题意很简单。就是求一个特殊序列，序列有三部分，非递减-最大-非递增
这题好奇怪。居然还限制代码长度，我用线段树提交总是失败。。。我用的树状数组才过的。还专门跑去学了下树状数组
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5+100;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
#define lowbit(x) (x&(-x))
int C[10000+10],n;
const int tn=10000;
void update(int pos,int val){
while(pos<=tn){
C[pos]=max(C[pos],val);
pos+=lowbit(pos);
}
}
int getmax(int pos){
int maxn=0;
while(pos>0){
maxn=max(maxn,C[pos]);
pos-=lowbit(pos);
}
return maxn;
}
int A[2*MAXN],B[MAXN];
int res[2][MAXN];
int solve(int pos){
B[0]=0;
for(int i=0;i<n;i++){
if(A[i+pos]!=10000)B[++B[0]]=A[i+pos];
}
memset(C,0,sizeof(C));
res[0][0]=0;
for(int i=1;i<=B[0];i++){
int t=getmax(10000-B[i]);
res[0][i]=max(res[0][i-1],t+B[i]);
update(10000-B[i],t+B[i]);
}
memset(C,0,sizeof(C));
res[1][B[0]+1]=0;
for(int i=B[0];i>=1;i--){
int t=getmax(10000-B[i]);
res[1][i]=max(res[1][i+1],t+B[i]);
update(10000-B[i],t+B[i]);
}
int ans=0;
for(int i=1;i<=B[0];i++){
ans=max(ans,res[0][i]+res[1][i+1]);
}
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;
}
|
