題目大意: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; }