Description
农夫约翰的奶牛喜欢玩硬币游戏，因此他发明了一种称为“Xoinc”的两人硬币游戏。 初始时，一个有N(5 <= N <= 2,000)枚硬币的堆栈放在地上，从堆顶数起的第I枚硬币的币值为$C_i$ (1 <= $C_i$ <= 100,000)。 开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币。如果第一个玩家只拿走堆顶的一枚硬币，那么第二个玩家可以拿走随后的一枚或两枚硬币。如果第一个玩家拿走两枚硬币，则第二个玩家可以拿走1，2，3，或4枚硬币。在每一轮中，当前的玩家至少拿走一枚硬币，至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时，游戏结束。 两个玩家都希望拿到最多钱数的硬币。请问，当游戏结束时，第一个玩家最多能拿多少钱呢？
Input
第1行：1个整数N
第2..N+1行：第i+1行包含1个整数$C_i$
Output
第1行：1个整数表示第1个玩家能拿走的最大钱数。
Sample Input
5
1
3
1
7
2
Sample Output
9
HINT
样例说明：第1个玩家先取走第1枚，第2个玩家取第2枚；第1个取走第3，4两枚，第2个玩家取走最后1枚。
题解
DP
设f[i][j]为还剩i个硬币这一次最多能取j个的最大价值
a[i]为硬币价值的后缀和
为了方便逆序读入
然后$f[i][j] = max(f[i][j - 1], a[i] - f[i - j][min(i - j, 2 * j)])$
搞定
#include <cstdio>
#include <algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int a[2005];
int f[2005][2005];
int main()
{
int n = read();
for (int i = n; i >= 1; i--) a[i] = read();
for (int i = 1; i <= n; i++) a[i] += a[i - 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
f[i][j] = max(f[i][j - 1], a[i] - f[i - j][min(i - j, j * 2)]);
printf ("%d\n", f[n][2]);
}