golB s'CBoriN

O(N^2)DP大水题啊！f[i][j]代表"还剩i个硬币，轮到的人被允许最多取j个硬币时，当前人可得到的最大钱数"

设最下方的k个硬币的总和为s[k] (0<=k<=N)

dp[0][0]=0

dp[i][j]=max(dp[i][j-1],//取个数<j

s[i]-dp[i-j][min(i-j,j*2)])//取个数=j

下面是我世界第一短代码

#include <cstdio>
int s[2001],N,f[2001][2001];
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
int main()
{
	scanf("%d",&N);
	for (int i=N;i;i--)
		scanf("%d",&s[i]);
	for (int i=2;i<=N;i++)
		s[i]+=s[i-1];
	for (int i=1;i<=N;i++)
		for (int j=1;j<=i;j++)
			f[i][j]=max(f[i][j-1],s[i]-f[i-j][min(i-j,j<<1)]);
	printf("%d\n",f[N][2]);
	return 0;
}