Tyvj1075

题目链接

分析：
这道题真的是十分刁钻
一眼博弈，然并卵

实际上我们这道题是从结束状态向初始状态转移的
首先明确状态的设定
用f[i][j]表示当前剩下i枚硬币，
上一轮对方取走j枚，面对此局面的人所能达到的最大价值

先考虑边界条件：
f[0][k]=0（1<=k<=n）
意思是最后我面对无子可取的情况，
对方上一轮取走k枚硬币，此时我能达到的最大值当然是0啦

目标：
f[n][1]
因为第一个人（指的是我）可以取1,2枚硬币，
所以我取时还剩下n枚硬币，1视作上一轮对方没取

转移方程：
f[i][j]=max{sum[i]-f[i-k][k]} (1≤k≤j*2)

解释：
sum[i]指的是
∑a[i](i=n-i+1 to n)

f[i][j]:本局我面对的是还剩下i枚硬币，
上一局对方取走j枚（此时我可以取1~j*2枚硬币），此时我的最大取值
f[i-k][k]:对手在我拿走k个硬币后
还剩下i-k个硬币的情况他最多能取的面值大小（sum一减就是我得的了）
实际上我真的不大明白这个机理

复杂度：O(n^3)

优化：在计算f[i][j-1]的时候，
1<=k<=2*j-2的部分已经计算过了
那么在转移f[i][j]的时候
只要在比较一下 sum[i]-f[i-(2*j-1)][2*j-1] 和 sum[i]-f[i-2*j][2*j]就可以了

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int n;
int f[2005][2005];
int c[2005],sum[2005];

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&c[i]);
    for (int i=n;i>=1;i--) sum[n-i+1]=sum[n-i]+c[i];
    int i,j,k;
    for (i=1;i<n;i++) f[0][i]=0;   //当前还有0个 
    //f[i][j]=max{sum[i]-f[i-k][k]}   1<=k<=2*j
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
        {
            f[i][j]=f[i][j-1];
            if (i-2*j+1>=0) f[i][j]=max(f[i][j],sum[i]-f[i-2*j+1][2*j-1]);
            if (i-2*j>=0) f[i][j]=max(f[i][j],sum[i]-f[i-2*j][2*j]);
        }       
    printf("%d",f[n][1]);
    return 0;
}