题解 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<bits/stdc++.h>

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<cstdio>

#include<iostream>

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]);

}

巴特西

题解 SP5271 XOINC - A Coin Game

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

最新文章

热门文章