题目描述

Farmer John's cows like to play coin games so FJ has invented with a new two-player coin game called Xoinc for them.
Initially a stack of N (5 <= N <= 2,000) coins sits on the ground; coin i from the top has integer value Ci (1 <= Ci <= 100,000).
The first player starts the game by taking the top one or two coins (C1 and maybe C2) from the stack. If the first player takes just the top coin, the second player may take the following one or two coins in the next turn. If the first player takes two coins then the second player may take the top one, two, three or four coins from the stack. In each turn, the current player must take at least one coin and at most two times the amount of coins last taken by the opposing player. The game is over when there are no more coins to take.
Afterwards, they can use the value of the coins they have taken from the stack to buy treats from FJ, so naturally, their purpose in the game is to maximize the total value of the coins they take. Assuming the second player plays optimally to maximize his own winnings, what is the highest total value that the first player can have when the game is over?

输入描述:

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: Ci

输出描述:

* Line 1: A single integer representing the maximum value that can be made by the first player.

示例1

输入
5
1
3
1
7
2
输出
9
说明
There are five coins with the values 1, 3, 1, 7, and 2.
The first player starts by taking a single coin (value 1). The opponent takes one coin as well (value 3). The first player takes two more coins (values 1 and 7 -- total 9). The second player gets the leftover coin (value 2-- total 5).

解答

DP： 1.状态：建立一个二维的状态(i,j)说明拿硬币的权力到达其中一名玩家时，桌面上还剩下编号为1~i(倒序，1为最底下的) 的硬币，
上一名玩家拿走了j枚硬币。
2.下一步的状态：那么这一个玩家在这一轮可以选择拿走1,2,3,4…2*j枚硬币，而他所能获得的最大硬币面值就是1~i所有的硬币面
值之和减去他完成此次操作后（设他取走了k枚硬币）到达状态(i-k,k)的另一名玩家所能获得的最大硬币数。
3.状态的转移：可是因为k的取值范围很大，所以不能直接枚举，不难发现(i,j-1)和(i,j)的状态只相差两种选择的可能，即下一步取走
2*j-1或2*j个硬币的这两种，只需要再比较一次这两种状态即可。
*状态转移方程：;
4.答案：答案则是在剩下1~n枚硬币时（初始状态）的（下一步可以选择1枚或两枚硬币）了。
AC代码： 


#include<bits/stdc++.h>
using namespace std;
int n,sum[3001],c[3001],dp[3001][3000]; //数组要开大一点，不然会WA；
int main()
{
    cin>>n;
    for(int i=n;i>=1;i--)cin>>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++)
        {
            dp[i][j]=dp[i][j-1];//重合部分
            int k=2*j-1;
            if(k<=i)dp[i][j]=max(dp[i][j],sum[i]-dp[i-k][k]);//新增状态
            k+=1;
            if(k<=i)dp[i][j]=max(dp[i][j],sum[i]-dp[i-k][k]);//新增状态
        }
    cout<<dp[n][1]<<endl;
    return 0;
}


来源：Twilight_