POJ 1440

題目大意：Steve和Digit輪流取甜甜圈，有n個，每次不能取超過m個（1<=m<=n<=100），他們游戲的規則是，Steve先取，每個人取了之後甜甜圈就放在自己那裡，當某個人取完最後一個以後，他吃掉自己那裡的甜甜圈並把對手的所有甜甜圈拿出來，重復這樣的過程，當一個人吃掉那對手的出來後，那一輪游戲是對手先手，求Steve能吃到的最多的甜甜圈。

用d[i][j][u][0]表示目前總共有i個甜甜圈，其中j個還未被取，u個在Steve處，且下一步到Steve走時，Steve能吃到的最多的甜甜圈，用d[i][j][u][1]表示目前總共有i個，j個未取，u個在Steve處，且下一步到Digit走時，Digit能吃到的最多的甜甜圈。

狀態轉移方程：

d[i][j][u][0]=max { max { i-d[i][j-v][u+v][1]},i-d[i-j-u][i-j-u][0][1]（如果這一步將剩下的都取完） }

d[i][j][u][1]=max { max {i-d[i][j-v][u][0]},i-d[i-j-q][i-j-q][0][1]（如果這一步將剩下的都取完） }（q=i-j-u，表示Digit持有的甜甜圈）

#include
#include
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;
}