题解 P2964 【[USACO09NOV]硬币的游戏A Coin Game】

Twilight_ · 2017-09-02 15:47:48 · 题解

嗯既然还没有题解那么我就来一发吧……

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个硬币的这两种，只需要再比较一次这两种状态即可。

*状态转移方程：dp[i][j]=max(dp[i][j],sum[i]-dp[i-k][k]，sum[i]-dp[i-k-1][k+1])(k==2\j-1);

4.答案：答案则是在剩下1~n枚硬币时（初始状态）的dp[n][1]（下一步可以选择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;
}