思路：y的可能性很少，只有10种类，，枚举y的位子，然后X和Z分别是一个上升和下降序列，可以分处理处正向递减，逆向递增的最大权值和。然后枚举断点求最大值即可。
可以用数状数组处理。
#include<stdio.h>#include<string.h>#include<iostream>#include<string>#include<queue>#include<cmath>#include<map>#include<algorithm>#include<vector>using namespace std;const int mmax = 100010;int C[10010];void init(){memset(C,0,sizeof C);}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 a[2*mmax];int b[mmax];int dp1[mmax];int dp2[mmax];int n;int solve(int id){int cnt=0;for(int i=id+1;i<id+n;i++){if(a[i]!=10000)b[cnt++]=a[i];}init();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]);}init();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;}
奋斗令我们的生活充满生机，责任让我们的生命充满意义！
