又是DP？

好吧，或者说是博弈论，但是我不会啊。

先搞个O（n^3）的记忆化搜索，然后瞎搞好像发现两个状态几乎一样？

竟然过了样例，然后竟然A了...

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 inline int read(){
 6     char chr=getchar();    int f=1,ans=0;
 7     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
 8     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
 9     return ans*f;
10 }void write(int x){
11     if(x<0) putchar('-'),x=-x;
12     if(x>9) write(x/10);
13     putchar(x%10+'0');
14 }int n,a[10005],dp[2001][2001],s[10005];//dp[i][j]---->the last one get j coins and there're i coins left;
15 int dfs(int x,int y){
16     if(dp[x][y]) return dp[x][y];
17     if(y==0) return 0;
18     if(x<(y<<1)) return dp[x][y]=s[x];
19     dp[x][y]=dfs(x,y-1);
20     dp[x][y]=max(dp[x][y],s[x]-min(dfs(x-(y<<1),(y<<1)),dfs(x-(y<<1)+1,(y<<1)-1)));
21     return dp[x][y];
22 }int main(){n=read();
23     for(register int i=n;i>=1;--i) a[i]=read();
24     for(register int i=1;i<=n;++i)s[i]=s[i-1]+a[i];
25     dfs(n,1);write(dp[n][1]);
26     return 0;
27 }