P2964 [USACO09NOV]A Coin Game S 题解
cjlak1o1
·
·
题解
由于巨佬语言过于高深，本蒟蒻这研究道题时间较为长，所以在这里本蒟蒻再用最朴素的语言重新讲解这道题。
题意描述
由 n 个硬币，每一个硬币都有一个面值，两个人轮流取硬币，第一个人可以取 1\sim 2 个硬币，设第一个人取了 j 个硬币，则第二个人可以取 1 \sim 2 \times j 个硬币，并以此类推，每一次当前的人都可以取 1 \sim 2 \times j 个硬币（ j 为上一个人取的硬币数），最后输出第一个人最多能拿多少面值。
构建dp
这道题不断在发生转移，所以我们想到用dp求解：
- 因为这是一道博弈论dp，满足两个人都很聪明，所以面对这样的问题，我们并不需要知道当前是谁在取，我们只需要让当前的这每一步最优即可。
- 由于如果是正着求的话，我们要记录的 2 倍会有很多很多种情况，记录下来十分麻烦，所以我们将这道题目的题意转换为两个人轮流放硬币，一个人放硬币时需要满足这一次放的硬币数的两倍大于等于上一次另一个人放的硬币数。
- 我们先记录前缀和， sum_i 记录放了 i 枚硬币后放的总面值数量。
- 用一个二维dp， dp[i][j] 表示已经放了 i 枚硬币，下一个人要放 j 枚硬币。也就是说这次最多放 2 \times j 个的情况
- 每一次转移, k 表示这一次取的硬币数量，枚举 k 的值从等于 1 到等于 2 \times j ，在 2 \times j 个 sum[i]-dp[i-k][k] 中取一个 max 值。 dp[i-k][k] 记录上一个人在当前这个人要放 k 枚硬币时上一个人最多能放的硬币数，用 sum[i] 减去 dp[i-k][k] 即为当前这个人放 k 个时放的总硬币数。
按照上述想法，时间复杂度为 O(n^3) ，这道题 n 有 2e3 ,没办法过去。所以我们要对dp进行优化。
优化dp
由于前两维是必须枚举的，所以我们考虑对第三个循环进行优化，我们观察一下 dp[i][j] 与 dp[i][j-1] 的关系。
$dp[i][j]$ 是枚举 $k$ 从等于 $1$ 到等于 $2 \times j$ ，在 $2\times j$ 个 $sum[i]-dp[i-k][k]$ 中取一个 $max$ 值。
所以从这里大家一定发现了， **$dp[i][j]$ 是严格包含 $dp[i][j-1]$ 的，我们只需要在 $dp[i][j-1]$ 的基础上继续枚举 $k=2 \times j-1$ 和 $k = 2 \times j$ 这两种状态即可。**
## code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+10;
int n,a[maxn];
int sum[maxn],dp[maxn][maxn];
inline int read()
{
int res=0,f=1;char c;
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) res=(res<<1)+(res<<3)+(c^48);
return res*f;
}
int main()
{
n=read();
for(int i=n;i>=1;i--) a[i]=read();//反过来读入，方便求前缀和
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];//sum[i]记录放了i个硬币后的总面值
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int k=2*j-1;
dp[i][j]=dp[i][j-1];//由上面分析可知，dp[i][j]严格包含了dp[i][j-1]
//在dp[i][j-1]的基础上更新两个状态。
if(k<=i) dp[i][j]=max(dp[i][j],sum[i]-dp[i-k][k]);
//当k<=i时，才能取max
if(k+1<=i) dp[i][j]=max(dp[i][j],sum[i]-dp[i-k-1][k+1]);
//当k+1<=i时，才能取max
}
/*for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
printf("dp[%d][%d]:%d\n",i,j,dp[i][j]);*/
printf("%d\n",dp[n][1]);
//这里dp[n][1]表示已经放了n个马上要再放1个，但还没有放。
//马上下一个人要放1个硬币，也就意味着上一次只能放1个或2个，即为第一次取的情况。
return 0;
}
```
**蒟蒻拙见，大佬勿喷。**