首页 > 代码库 > SCU - 4441 Necklace(树状数组求最长上升子数列)
SCU - 4441 Necklace(树状数组求最长上升子数列)
Necklace
frog has \(n\) gems arranged in a cycle, whose beautifulness are \(a_1, a_2, \dots, a_n\). She would like to remove some gems to make them into a beautiful necklace without changing their relative order.
Note that a beautiful necklace can be divided into \(3\) consecutive parts \(X, y, Z\), where
- \(X\) consists of gems with non-decreasing beautifulness,
- \(y\) is the only perfect gem. (A perfect gem is a gem whose beautifulness equals to \(10000\))
- \(Z\) consists of gems with non-increasing beautifulness.
Find out the maximum total beautifulness of the remaining gems.
Input
The input consists of multiple tests. For each test:
The first line contains \(1\) integer \(n\) (\(1 \leq n \leq 10^5\)). The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\). (\(0 \leq a_i \leq 10^4\), \(1 \leq \textrm{number of perfect gems} \leq 10\)).
Output
For each test, write \(1\) integer which denotes the maximum total remaining beautifulness.
Sample Input
6
10000 3 2 4 2 3
2
10000 10000
Sample Output
10010
10000
#include <bits/stdc++.h> #define met(a,b) memset(a,b,sizeof a) using namespace std; typedef long long ll; const int N = 1e5+50; int C[N]; int dp1[N],dp2[N],b[N],a[2*N]; int n,m,k; int low_bit(int x) { return x&(-x); } void updata(int pos,int val) { for(int i=pos;i<=10000;i+=low_bit(i)) C[i]=max(C[i],val); } int get_max(int pos) { int ans=0; for(int i=pos;i>0;i-=low_bit(i)) ans=max(ans,C[i]); return ans; } int solve(int id) { met(C,0); int cnt=0; for(int i=id+1;i<id+n;i++) { if(a[i]!=10000) b[cnt++]=a[i]; } dp1[0]=b[0]; updata(10000-b[0],b[0]); for(int i=1;i<cnt;i++) { dp1[i]=get_max(10000-b[i])+b[i]; updata(10000-b[i],dp1[i]); } met(C,0); dp2[cnt-1]=b[cnt-1]; updata(10000-b[cnt-1],b[cnt-1]); for(int i=cnt-2;i>=0;i--) { dp2[i]=get_max(10000-b[i])+b[i]; updata(10000-b[i],dp2[i]); } int ans=0; for(int i=1;i<cnt;i++) dp1[i]=max(dp1[i],dp1[i-1]); for(int i=cnt-2;i>0;i--) dp2[i]=max(dp2[i],dp2[i+1]); dp2[cnt]=0; for(int i=0;i<cnt;i++) ans=max(ans,dp1[i]+dp2[i+1]); ans=max(ans,dp2[0]); return ans+10000; } int main() { while(~scanf("%d",&n)) { for(int i=0;i<n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; } int ans=0; for(int i=0;i<n;i++) { if(a[i]==10000) { ans=max(ans,solve(i)); } } printf("%d\n",ans); } return 0; }
SCU - 4441 Necklace(树状数组求最长上升子数列)