题目回顾

Steve和Digit玩一个分甜甜圈的游戏：

• 初始有 n 个甜甜圈，每次可以取 1 到 m 个。
• 玩家轮流取甜甜圈，取出的甜甜圈放在自己的一边。
• 关键规则：如果某玩家清空盒子，他可以吃掉自己取出的甜甜圈，而另一名玩家必须把自己的甜甜圈放回盒子，并由输家开始下一轮。
• 游戏持续到所有甜甜圈被吃完，目标是吃到最多的甜甜圈。
• Steve先手，双方都采取最优策略，求Steve最多能吃到多少个甜甜圈。

解题思路

这道题属于博弈论 + 动态规划（DP）问题。我们需要计算在最优策略下，Steve能吃到的最多甜甜圈数量。由于游戏规则较为复杂，直接递归或暴力搜索会非常低效，因此采用记忆化DP来优化计算。

DP状态定义

代码中的 d[i][j][u][0/1] 是一个四维DP数组，其含义如下：

• i：当前盒子中剩余的甜甜圈总数。
• j：当前轮次剩余的甜甜圈数量（可能和 i 不同，因为某些甜甜圈可能被放回）。
• u：Digit（对手）已经取出但尚未吃掉的甜甜圈数量（即会被放回盒子的数量）。
• 0/1：表示当前是Steve（0）还是Digit（1）的回合。

d[i][j][u][0] 表示：

• 当前盒子剩余 i 个甜甜圈，当前轮剩余 j 个，Digit有 u 个待放回，且轮到Steve取时，Steve能吃到的最多甜甜圈数量。

d[i][j][u][1] 类似，但表示Digit的最优解。

状态转移分析

1. Steve的回合（d[i][j][u][0]）：

   • Steve可以取 1 到 min(m, j) 个甜甜圈。
   • 如果Steve取 v 个：
     • 如果 v == j（清空盒子）：
       • Steve吃掉自己取的 v 个，Digit必须放回 u 个甜甜圈。
       • 下一轮由Digit开始，盒子剩余 u 个甜甜圈。
       • 此时Steve的总收益 = v + (总甜甜圈 - Digit在下一轮的最优解)。
     • 如果 v < j（未清空盒子）：
       • Digit的回合，盒子剩余 i 个，当前轮剩余 j - v 个，Steve的待放回甜甜圈增加 v 个。
       • Steve的总收益 = 总甜甜圈 - Digit在下一状态的最优解。
   • Steve会选择使自己收益最大的 v。

2. Digit的回合（d[i][j][u][1]）：

   • 类似Steve的回合，但Digit的目标是最小化Steve的收益。
   • 如果Digit清空盒子：
     • Digit吃掉自己取的 v 个，Steve放回 u 个甜甜圈。
     • 下一轮由Steve开始，盒子剩余 u 个。
   • 如果未清空：
     • Steve的回合，盒子剩余 i 个，当前轮剩余 j - v 个，Digit的待放回甜甜圈增加 v 个。
   • Digit会选择使Steve收益最小的 v。

初始化

• d[0][0][0][0] = d[0][0][0][1] = 0：没有甜甜圈时，双方收益为0。

最终答案

• d[n][n][0][0]：初始状态，盒子有 n 个甜甜圈，Steve先手，Digit没有待放回的甜甜圈。

#include<stdio.h>
#include<stdlib.h>
int d[103][103][103][2];
int main(void)
{
	int i,j,u,v,p,q,m,n,maxp;
	while(scanf("%d%d",&n,&m)==2)
	{
		d[0][0][0][0]=d[0][0][0][1]=0;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=i;j++)
			{
				p=i-j;
				for(u=0;u<=p;u++)
				{
					q=i-j-u;
					maxp=0;
					for(v=1;v<=m;v++)
					{
						if(v>j)
						{
							break;
						}
						else if(v==j)
						{
							if(i-d[i-u-v][i-u-v][0][1]>maxp)
							{
								maxp=i-d[i-u-v][i-u-v][0][1];
							}
						}
						else
						{
							if(i-d[i][j-v][u+v][1]>maxp)
							{
								maxp=i-d[i][j-v][u+v][1];
							}
						}
					}
					d[i][j][u][0]=maxp;
					maxp=0;
					for(v=1;v<=m;v++)
					{
						if(v>j)
						{
							break;
						}
						else if(v==j)
						{
							if(i-d[i-q-v][i-q-v][0][0]>maxp)
							{
								maxp=i-d[i-q-v][i-q-v][0][0];
							}
						}
						else
						{
							if(i-d[i][j-v][u][0]>maxp)
							{
								maxp=i-d[i][j-v][u][0];
							}
						}
					}
					d[i][j][u][1]=maxp;
				}
			}
		}
		printf("%d\n",d[n][n][0][0]);
	}
	return 0;
}