UVa:10534 Wavio Sequence

发布时间:2016-12-6 22:19:21 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVa:10534 Wavio Sequence",主要涉及到UVa:10534 Wavio Sequence方面的内容,对于UVa:10534 Wavio Sequence感兴趣的同学可以参考一下。

一开始用了O(n^2)的算法超时了两次,后来脑子抽了居然用升降序列相同来判答案又WA了一次。   这个题也是LIS,但是只能用O(nlgn)的算法。   一开始以为O(nlgn)只能求解整个序列的最长递增,其实不然,以p[]表示原序列,lis[]表示辅助数组,那么lis[i]表示以lis[i]结尾的最长递增序列长度是i(1<=i<=n),而每个lis[i]又是由每个p[j](1<=j<=n)对应而来的。当然这个过程中的每个lis[i]又可能被替换更新,我们只需要记录下它出现时对应的长度i即可。最终可以得到每个以p[j]结尾的最长递增序列的长度。 到这里就完成一半了。 然后就需要求以p[j]为开头的最长递减序列的长度。 用之前求以p[j]结尾的最长递增序列的长度的方法是从1遍历到n,那么如果从n遍历到1,其实就是得到以p[j]为开头的最长递减序列的长度。 这样另一半也就解决了。 以每个数字为中心的Wavio Sequence长度很明显是min(升lis,降lis)*2-1,只需要输出它的最大值即可。   另外这里用到了 iterator lower_bound( const key_type &key ): 返回一个迭代器,指向键值>= key的第一个元素。 iterator upper_bound( const key_type &key ):返回一个迭代器,指向键值> key的第一个元素。 这两个函数,名字差不少,功能却只差一个等号。。 注意它是返回地址,所以如果要求下标还需要减去首地址。   这个题是要求相邻元素不能相同,也就是严格递增递减的,所以在lis数组中相同元素应该被替换而不是再增加一个,所以要返回键值>= key(带着等号)这种情况,所以用了lower_bound。   #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define INF 0x7f7f7f7f using namespace std; int p[10005],a[10005],b[10005]; int lis[10005]; int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=1; i<=n; ++i) scanf("%d",&p[i]); memset(lis,INF,sizeof(lis)); lis[0]=-INF; for(int i=1; i<=n; ++i) { int x=lower_bound(lis,lis+n+1,p[i])-lis; lis[x]=p[i]; a[i]=x; } memset(lis,INF,sizeof(lis)); lis[0]=-INF; for(int i=n; i>=1; --i) { int x=lower_bound(lis,lis+n+1,p[i])-lis; lis[x]=p[i]; b[i]=x; } int ans=1; for(int i=1; i<=n; ++i) ans=max(ans,min(a[i],b[i])*2-1); printf("%d\n",ans); } return 0; }  

上一篇:logback那些事
下一篇:android内置搜索对话框(浮动搜索)例子

相关文章

相关评论