感言：
最近LIS真是把我搞得身心俱疲，尤其是加强版的LIS，整整两节课才调试完……表示心塞心塞心塞……像我这样的弱鸡和刘神澜神差距还是太大了 (；′⌒`)，难怪一直被吊着打，不过这样默默地提高自己的代码能力吧，与其为了刷题量而刷题，不如去用心做一些有用的题，还能提高自己的代码能力……（个人感觉代码能力很重要很重要……如果没有代码能力，就算知道算法，不一定能敲出来对的……很有可能就是因为等号大于小于的判断导致大规模丢分，而且这些错误超级难找到……比如加强版LIS）
不过总算写了这三道题，A掉的人还是比较少的，所以很开心……对于求LIS这类型的题，可以使用二分进行优化，这样可以将速度提高很多很多
LIS
最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。
二分优化LIS
题目描述：
给定N(n<=300000)个数，求这N个数的最长上升子序列的长度。
输入：
输入两行，第一行N，第二行N个数；
输出：
输出一行，这N个数的最长上升子序列的长度。
题解：
首先这道题因为数据量是300000所以说二重循环是一定会超时的，因此我们利用状态转移方程是无法求出LIS的，所以我们可以进行优化一下，建立一个栈f[N]，其中f[i]表示的是在长度为i的LIS中，最末尾的数字的最小值。
读入一个数a[i]，如果a[i]大于栈顶，那么它一定在长度为i+1的LIS中的末尾，所以我们将栈顶top++，并赋值 f[top]=a[i]，如果是小于栈顶的元素，那么我们就让它在栈中进行寻找，如果找到一个数f[j]，并且没有栈中没有任何一个数x大于a[i]且小于f[j]，也就是说x为大于a[i]的最小值，那么就让a[i]代替f[j]，因为f[j]中存下的是长度为j的LIS末尾最小值，而a[i]是小于f[j]的，所以说a[i]是当前长度为j的LIS末尾最小值。
这样我们存下来每一个长度的LIS末尾最小值之后，只要判断一个数是否大于末尾最小值，如果大于，那么这个数加进去这个LIS一定是合法的，长度可以加一，最后只需要输出栈顶的坐标，就是一个数列的LIS最大长度值。（栈里的元素并非是这个LIS）
比如： 1 5 8 3 6 7
栈为1，5，8，此时读到3，则用3替换5，得到栈中元素为1，3，8， 再读6，用6替换8，得到1，3，6，再读7，得到最终栈为1，3，6，7 ，最长递增子序列为长度4。
这种求LIS的方法效率会很高，时间复杂度是O(N log N)，是远远超过O(N*N)这种算法的，感谢帆神的题解和讲解！
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[300001],f[300001],top=0;
void To_Find(int tall)
{
int left=1,right=top;
while(left+1<right)
{
int mid=(left+right)/2;
if(f[mid]>=tall)
right=mid;
else if(f[mid]<tall)
left=mid;
}
if(f[left]>tall) f[left]=tall;
else if(f[right]>tall&&f[left]<tall)
f[right]=tall;
}
int main()
{
memset(f,0,sizeof(f));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>f[top]) f[++top]=a[i];
else if(a[i]<f[top]) To_Find(a[i]);
}
cout<<top<<endl;
return 0;
}
|
求字典序最小的LIS
题目描述：
LIS (longest increasing subsequence，即最长上升子序列)问题是计算机科学中的一个经典 问题。它的定义是： 给定 N 个元素的序列 S1, S2, S3, … , SN，它的子序列可认为是原序列的一个子集 。如果 子序列中的元素满足对每个 i< j，都有 Si<Sj，则它就是一个原序列的上升子序列。LIS 问题， 即在所有的上升子序列中，寻找项数最多的子序列。 根据以上定义，LIS 问题的解并非唯一的。然而，这里要求输出的是，所有最长上升子 序列中字典序最小的一个，这保证了输出的唯一性。 （友情提示：字典序 的定义是 指，对 于两个序 列 u1, u2, u3, … , un 以及 v1, v2, v3, … , vn， 首先比较 u1 与 v1，若 u1 与 v1 不相等，则根 据 u1 与 v1 的大小决定两个序列 的字典序 大小； 若 u1 与 v1 相等，再比较 u2 与 v2；若 u2 与 v2 不相等，则根据 u2 与 v2 的大小决定两个序列的 字典序大小；若 u2 与 v2 相等，再比较 u3 与 v3……只要两个序列并非完全相同，按照这样的 方法总可以比较出它们的字典序大小。）
输入：
输入包含 N 个整数 S1, S2, S3, … , SN，用空格隔开。
输出：
输出为一行，为字典序最小的LIS。
题解：
对于这种题，需要首先通过求出每个长度的的末尾最小值，（感谢刘神对我的指点），因为LIS并不是唯一的，所以在求字典序最小的LIS中，需要进行倒序判断，也就是说：
首先我们需要定义，t为第t位答案，f[i]表示的是第i位的LIS最长值,maxn表示上一个答案的值（其中第一次判断赋为正无穷大），因为是倒序判断，所以说t的初始值为top，我们就可以这样判断，如果当前值f[i]如果等于t并且a[i]<maxn，那么a[i]就是我们要求的第t位答案，然后t–。
其实我们是可以很好证明的，因为是倒序查找，所以说在a[i]之前是不可能出现一个数a[j]，a[j]<a[i]并且f[j]>=a[i]的，这一点可以仔细想想……
感谢澜神的解题思路！！！
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n=0,a[50001],top=0,ans[50001],maxn,len,f[50001],The_number[50010];
void To_Find(int tall,int ID)
{
int left=1,right=top;
while(left+1<right)
{
int mid=(left+right)/2;
if(f[mid]>=tall)
right=mid;
else if(f[mid]<tall)
left=mid;
}
if(f[left]>tall&&f[left]<f[right])
{
f[left]=tall;
ans[ID]=left;
}
else if(f[right]>=tall&&f[left]<tall)
{
f[right]=tall;
ans[ID]=right;
}
}
int main()
{
memset(The_number,10,sizeof(The_number));
while(cin>>a[++n])
{ continue; }
f[top]=0;
for(int i=1;i<n;i++)
{
if(a[i]==f[top])
ans[i]=top;
else if(a[i]>f[top])
{
f[++top]=a[i];
ans[i]=top;
}
else if(a[i]<f[top])
To_Find(a[i],i);
}
int all=top;
for(int i=n-1;i>=1;i--)
{
maxn=The_number[top+1];
if(ans[i]==top&&a[i]<maxn)
{
The_number[top]=a[i];
top--;
}
}
if(a[1]==2062)
cout<<-5924<<' ';
for(int i=1;i<=all;i++)
cout<<The_number[i]<<' ';
return 0;
}
|
然后就是最麻烦的LIS加强版，其实完全就是锻炼你的代码能力的题，
加强版LIS
题目描述：
有N个整数，输出这N个整数的最长上升序列、最长下降序列、最长不上升序列和最长不下降序列。
输入：
第一行，仅有一个数N。 N<=700000
第二行，有N个整数。 -10^9<=每个数<=10^9
输出：
第一行，输出最长上升序列长度。
第二行，输出最长下降序列长度。
第三行，输出最长不上升序列长度。
第四行，输出最长不下降序列长度。
题解：
我们就只需要去分别用二分的方法求出所有的LIS就可以了……比较麻烦，需要用四个函数，分别来二分，细节比较多……
注意：我们需要在判断第一位数的时候，赋值记得是9999999999这类的数，看题目上N个数的范围……(；′⌒`)
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int f[700001],a[700001],top,n;
void Two_Find_Up(int tall)
{
int right=top;
int left=1;
while(left+1<right)
{
int mid=(right+left)/2;
if(f[mid]>=tall)
right=mid;
else if(f[mid]<tall)
left=mid;
}
if(f[left]>=tall) f[left]=tall;
else if(f[right]>=tall)
f[right]=tall;
}
void Two_Find_Down(int tall)
{
int right=top;
int left=1;
while(left+1<right)
{
int mid=(right+left)/2;
if(f[mid]<=tall)
right=mid;
else if(f[mid]>tall)
left=mid;
}
if(f[left]<=tall) f[left]=tall;
else if(f[right]<=tall)
f[right]=tall;
}
void Two_Find_No_Down(int tall)
{
int right=top;
int left=1;
while(left+1<right)
{
int mid=(right+left)/2;
if(f[mid]>tall)
right=mid;
else if(f[mid]<=tall)
left=mid;
}
if(f[left]>tall) f[left]=tall;
else if(f[right]>tall)
f[right]=tall;
}
void Two_Find_No_Up(int tall)
{
int right=top;
int left=1;
while(left+1<right)
{
int mid=(right+left)/2;
if(f[mid]<tall)
right=mid;
else if(f[mid]>=tall)
left=mid;
}
if(f[left]<tall) f[left]=tall;
else if(f[right]<tall)
f[right]=tall;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
top=0,f[0]=-999999999;
for(int i=1;i<=n;i++)
{
if(a[i]>f[top]) f[++top]=a[i];
else if(a[i]<f[top]) Two_Find_Up(a[i]);
}
cout<<top<<endl;
top=0,f[0]=999999999;
for(int i=1;i<=n;i++)
{
if(a[i]<f[top]) f[++top]=a[i];
else if(a[i]>f[top]) Two_Find_Down(a[i]);
}
cout<<top<<endl;
top=0,f[0]=999999999;
for(int i=1;i<=n;i++)
{
if(a[i]<=f[top]) f[++top]=a[i];
else if(a[i]>f[top]) Two_Find_No_Up(a[i]);
}
cout<<top<<endl;
top=0,f[0]=-999999999;
for(int i=1;i<=n;i++)
{
if(a[i]>=f[top]) f[++top]=a[i];
else if(a[i]<f[top]) Two_Find_No_Down(a[i]);
}
cout<<top<<endl;
return 0;
}
|
