首页 > 代码库 > SCU 4441 Necklace
SCU 4441 Necklace
最长上升子序列，枚举。
因为$10000$最多只有$10$个，所以可以枚举采用哪一个$10000$，因为是一个环，所以每次枚举到一个$10000$，可以把这个移到最后，然后算从前往后的$LIS$和从后往前的$LIS$，然后枚举一下哪里断开就可以了。
#include<bits/stdc++.h>using namespace std;int a[100010],n;int b[100010],dp1[100010],dp2[100010];int c[40010],u,mx1[100010],mx2[100010];void get(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R) { u=max(u,c[rt]); return ; } int m = (l+r)/2; if(L<=m) get(L,R,l,m,2*rt); if(R>m) get(L,R,m+1,r,2*rt+1);}void update(int pos,int val,int l,int r,int rt){ if(l==r) { c[rt] = val; return ; } int m = (l+r)/2; if(pos<=m) update(pos,val,l,m,2*rt); if(pos>m) update(pos,val,m+1,r,2*rt+1); c[rt]=max(c[2*rt],c[2*rt+1]);}int main(){ while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); int ans=10000; for(int i=1;i<=n;i++) { if(a[i]!=10000) continue; for(int j=i+1;j<=n;j++) b[j-i]=a[j]; for(int j=1;j<=i;j++) b[n-i+j]=a[j]; for(int j=1;j<=n-1;j++) if(b[j]==10000) b[j]=0; memset(dp1,0,sizeof dp1); memset(dp2,0,sizeof dp2); memset(c,0,sizeof c); for(int j=1;j<=n-1;j++) { u=0; get(b[j],10000,0,10000,1); dp1[j] = u + b[j]; update(b[j],dp1[j],0,10000,1); } memset(c,0,sizeof c); for(int j=n-1;j>=1;j--) { u=0; get(b[j],10000,0,10000,1); dp2[j] = u + b[j]; update(b[j],dp2[j],0,10000,1); } for(int j=1;j<=n-1;j++) mx1[j]=max(mx1[j-1],dp1[j]); for(int j=n-1;j>=1;j--) mx2[j]=max(mx2[j+1],dp2[j]); for(int j=1;j<=n-1;j++) { ans=max(ans,10000+dp1[j]); ans=max(ans,10000+dp2[j]); } for(int j=1;j<=n-2;j++) ans=max(ans,10000+mx1[j]+mx2[j+1]); } printf("%d\n",ans); } return 0;}
SCU 4441 Necklace
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。