首页 > 代码库 > “盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛 F
“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛 F
如果一个序列有奇数个正整数组成,不妨令此序列为a 1 ,a 2 ,a 3 ,...,a 2?k+1 (0<=k ),并且a 1 ,a 2 ...a k+1 是一个严格递增的序列,a k+1 ,a k+2 ,...,a 2?k+1 ,是一个严格递减的序列,则称此序列是A序列。
比如1 2 5 4 3就是一个A序列。
现在Jazz有一个长度为n 的数组,他希望让你求出这个数组所有满足A序列定义的子序列里面最大的那个长度。(子序列可以不连续)
比如1 2 5 4 3 6 7 8 9,最长的A序列子串是1 2 5 4 3。
多组输入,每组两行。
第一行是n
,表示给的数组的长度。
第二行有n
个数(int范围),即给你的数组。
1<=n<=500000
。
每组输入输出一行,即最长的A序列子串的长度。
复制
9 1 2 5 4 3 6 7 8 9
5
解法:
1 要求应该是对称形式,左升右降
2 当然要用LIS
3 我们对每一个点当做最高点,看从左和从右最长能到多少
3 因为是对称,那么最大值不要,我们用最小的,比如从左边开始最长是5,右边是3,那么我们选3(左边能到5,到3没问题)
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 const int maxn=500005; 5 int a[maxn]; 6 int b[maxn],c[maxn],d[maxn],e[maxn]; 7 int Search(int num,int low,int high){ 8 int mid; 9 while(low<=high){ 10 mid=(low+high)/2; 11 if(num>b[mid]) low=mid+1; 12 else high=mid-1; 13 } 14 return low; 15 } 16 void DP(int n,int* x,int a[]) 17 { 18 int i,len,pos; 19 b[1]=a[1]; 20 x[1]=1; 21 len=1; 22 for(i=2;i<=n;i++) 23 { 24 if(a[i]>b[len])//如果a[i]比b[]数组中最大还大直接插入到后面即可 25 { 26 len=len+1; 27 b[len]=a[i]; 28 pos=len; 29 } 30 else//用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置 31 { 32 pos=Search(a[i],1,len); 33 b[pos]=a[i]; 34 } 35 x[i]=pos; 36 } 37 } 38 int main(){ 39 int n; 40 while(~scanf("%d",&n)){ 41 for(int i=1;i<=n;++i) {scanf("%d",&a[i]);e[i]=a[i];} 42 reverse(e+1,e+n+1); 43 DP(n,c,a); 44 memset(b,0,sizeof(b)); 45 DP(n,d,e); 46 int Maxlen=-1; 47 reverse(d+1,d+n+1); 48 for(int i=1;i<=n;i++){ 49 int ans=min(c[i],d[i]); 50 Maxlen=max(Maxlen,2*ans-1); 51 } 52 printf("%d\n",Maxlen); 53 } 54 return 0; 55 }
“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛 F
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。