试题分析
容易发现性质,选择的是一段区间,但是贪心无法去维护这件事情,所以考虑$dp$,且我们只要去设计关于$JOI$的选择。
设$dp(i,j)$为现在要在$[l,r]$区间内选择,然后就可以随便写了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
inline int read(){
int f=,ans=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}
return f*ans;
}
const int N=;
int dp[N][N],n,val[N],maxn;
int dfs(int l,int r){
if(l==r) return dp[l][r]=val[l];
if(l+==r) return dp[l][r]=max(val[l],val[r]);
if(dp[l][r]!=-) return dp[l][r];
int res=;
if(val[l+]>val[r]) res=max(res,dfs(l+,r)+val[l]);
else res=max(res,dfs(l+,r-)+val[l]);
if(val[l]<val[r-]) res=max(res,dfs(l,r-)+val[r]);
else res=max(res,dfs(l+,r-)+val[r]);
return dp[l][r]=res;
}
signed main(){
memset(dp,-,sizeof(dp));
n=read();
for(int i=;i<=n;i++) val[i]=val[i+n]=read();
for(int i=;i<=n+;i++){
maxn=max(maxn,dfs(i,i+n-));
}
printf("%lld\n",maxn);
}