题目描述
农夫约翰的奶牛喜欢玩硬币游戏.
初始时，一个有N枚硬币的堆栈放在地上，从堆顶数起的第i枚硬币的币值 为Ci
开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币.如果第一个玩家只拿走堆顶的 一枚硬币，那么第二个玩家可以拿走随后的一枚或两枚硬币.如果第一个玩家拿走两枚硬币，则第二个玩家可以拿走1，2，3，或4枚硬币.在每一轮中，当前的玩家至少拿走一枚硬币，至多拿 走对手上一次所拿硬币数量的两倍.当没有硬币可拿时，游戏结束.
两个玩家都希望拿到最多钱数的硬币.请问，当游戏结束时，第一个玩家最多能拿多少钱 呢？
输入输出格式
输入格式：
-
Line 1: A single integer: N
- Lines 2..N+1: Line i+1 contains a single integer: C_i
输出格式：
- Line 1: A single integer representing the maximum value that can be made by the first player.
代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=2005; inline void read(int &x){ x=0; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} } int n; int c[maxn],sum[maxn],f[maxn][maxn]; int main(){ read(n); for(int i=n;i>0;--i) read(c[i]); for(int i=1;i<=n;++i) sum[i]=sum[i-1]+c[i]; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j){ f[i][j]=f[i][j-1]; int k=(j<<1)-1; if(k<=i) f[i][j]=max(f[i][j],sum[i]-f[i-k][k]); k=(j<<1); if(k<=i) f[i][j]=max(f[i][j],sum[i]-f[i-k][k]); } printf("%d ",f[n][1]); return 0; }