【P2964】硬币的游戏（DP+前缀和）

一道DP，思维难度真是不小。

首先对于这个题的数据，我们可以发现差不多可以支持n^2logn，但是貌似也不会有这种复杂度的线性DP（至少这个题看上去不是这样）。所以我们考虑N^2做法。因为求得是价值和，所以很明显要使用前缀和。

我们用f[i][j]来表示从下往上i枚硬币时轮到第一个人选，上一次对方取了j枚硬币时的情况。则根据题意这个人此时能取t枚（t<=i），此时这个人可以去那么此时取到的最大值就是max（f[i][j],f[i-t][t]）。又因为t的数目确实比较庞大，无法一个个枚举，所以考虑是否可以转移，容易看出，f[i][j]与f[i][j-1]能取的只差了j×2和j×2-1这两种状态，所以可以摒弃循环而直接用if判断来转移。

代码实际上还是比较短的：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define re register

using namespace std;

int f[][],a[],s[],n,m;

int main()

{

    cin>>n;

    for(re int i=n;i>=;i--) cin>>a[i];

    for(re int i=;i<=n;i++) s[i]=s[i-]+a[i];

    for(re int i=;i<=n;i++)

    {

         for(re int j=;j<=n;j++)

         {

             f[i][j]=f[i][j-];

             int t=*j-;

             if(t<=i)

             f[i][j]=max(f[i][j],s[i]-f[i-t][t]);

             t++;

             if(t<=i)

             f[i][j]=max(f[i][j],s[i]-f[i-t][t]);

         }

    }

    cout<<f[n][];

}

巴特西

【P2964】硬币的游戏（DP+前缀和）

最新文章

热门文章