SP5271 XOINC - A Coin Game

双倍经验：P2964 [USACO09NOV]硬币的游戏A Coin Game

O3做法（TLE）：枚举i,j,k，即剩下i枚金币，上一轮选了j枚金币，这一轮选k（1<=k<=j * 2）枚金币。

O2做法 1：容易发现，对于【j-1】，k枚举范围为1~2j-2；对于【j】，k的范围只增加了2j-1，2j两项，可以枚举i，j，再由【j-1】的状态继续判断2j-1，2j两项（sum为前缀和）

#include
using namespace std;
int n,sum[2001],c[2001],dp[2001][2001]; 
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;
}

O2做法 2：剩下第i枚金币，本次最多在其中取j个，要么由最多取j-1枚的状态转移，要么取j个，则下一轮最多取min(i-j,j<<1)枚

#include
#include
using namespace std;
int n,s[2001],f[2001][2001];
int main() {
    scanf("%d",&n);
    for (int i=n; i; i--) scanf("%d",&s[i]);//倒序输入
    for (int i=2; i<=n; i++) s[i]+=s[i-1];
    for (int i=1; i<=n; i++)
        for (int j=1; j<=i; j++)//本次取的个数不超过剩下的个数
            f[i][j]=max(f[i][j-1],s[i]-f[i-j][min(i-j,j<<1)]);
    printf("%d",f[n][2]);
}