题解
设$dp(i,j)$表示还剩$i$个，之前选了$j$个的状态。
正面非常不好做，所以要用这个倒着推的状态。
转移只要$2$个，因为其他转移之前已经包含了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int dp[2005][2005],n,a[2005],sum[2005],que[4000005][2],f=0,r=0;
void init(){
n=read();
sum[0]=0;
for(int i=n;i>=1;i--)a[i]=read();
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
//正面不好写
}
void solve(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j]=dp[i][j-1];
if(i-2*j>=0)dp[i][j]=max(dp[i][j],sum[i]-dp[i-2*j][2*j]);
if(i-2*j+1>=0)dp[i][j]=max(dp[i][j],sum[i]-dp[i-2*j+1][2*j-1]);
}
}
printf("%d\n",dp[n][1]);
}
int main(){
init();
solve();
return 0;
}