UVA - 10534 Wavio Sequence

Posted on | In , ,

思路

LIS变形，本来想O(n^2)暴力踩10^8结果TLE的悲伤故事，所以学习了一下O(nlogn)的LIS求法。
对于最朴素的做法我们使用dp在n^2时间可以求出一个数列的LIS，程序如下

1
2
3
4
5
6
7
8
int dp[MAXN],maxs=-1;
memset(dp,1,sizeof(dp));   //假装可以这么写
for(int i=0;i<n;i++){
    for(int j=0;j<i;j++){
        if(dp[i]>dp[j])dp[i]=max(dp[i],dp[j]+1);
    }
    maxs=max(dp[i],maxs);
}

然而我们还有更机智的做法。考虑维护一个单调增的数列q[MAXN],令一个计数器cnt=0，我们从头扫到尾，然后会有两种情况:

  1. !cnt||a[i]>q[cnt-1],那我们直接在数列尾部加上a[i]，得到的数列就是当前最大公共子序列
  2. 不然我们能得到a[i]小于等于q数组最后一个元素。我们在这里对q进行二分查找，找到第一个大于等于a[i]的数然后将该位置的数替换为a[i]。

这样就能nlogn求出数列的LIS，我们维护1-i的递增子序列长度和i-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
#include <bits/stdc++.h>
#define ms(a,val) memset(a,val,sizeof(a))
#define ll long long
#define INF 0x7fffffff

using namespace std;

const int MAXN=10005;

int a[MAXN],dp1[MAXN],dp2[MAXN],q[MAXN];

int main(){
	int n;
	while(~scanf("%d",&n)){
		int maxs=-1,cnt=0;
		ms(q,0);
		for(int i=0;i<n;i++)scanf("%d",&a[i]);
		for(int i=0;i<n;i++){
			if(!cnt||q[cnt-1]<a[i])q[cnt++]=a[i],dp1[i]=cnt;
			else{
                int pos=lower_bound(q,q+cnt,a[i])-q;
                q[pos]=a[i];
                dp1[i]=pos+1;
			}
		}
		maxs=-1;
		cnt=0;
		for(int i=n-1;i>=0;i--){
			if(!cnt||q[cnt-1]<a[i])q[cnt++]=a[i],dp2[i]=cnt;
			else{
                int pos=lower_bound(q,q+cnt,a[i])-q;
                q[pos]=a[i];
                dp2[i]=pos+1;
			}
		}
		maxs=1;
		for(int i=0;i<n;i++){
            //cout<<dp1[i]<<" "<<dp2[i]<<endl;
            maxs=max(maxs,2*min(dp1[i],dp2[i])-1);
		}
		printf("%d\n",maxs);
	}
	return 0;
}