博弈dp分析和总结

《博弈DP》aCHVlInternationalCollegiateCIWI11ProgrammingContesteventsponsorJiangnanUniversitLiyang2014/10/24cout«dfs(lzn)«endl;return0;题目大意：有B个盒子里面放有G种颜色的宝石，两个人轮流选一个盒子将其中的宝石取出来放到一个锅里，然后其中没有S个相同颜色的宝石,它们就会聚合在一起变成一个魔法石（可能产生多个魔法石且锅里有可能有剩余的宝石），然后本轮的得分就是产生的魔法石的数量，目如果本轮某个人拿到了魔法石的话,那么下一轮他还可以继续选择盒子放入宝石，知道他在某一轮没有拿到魔法石，现在问两个人都采用最优策略的情况下，到最后先拿的那个人的得分与后拿的人的得分的差是多少。constintmaxn=22;intb,g,s;vector<int>bg[maxn];intscore[l«maxn];intsum[maxn];boolvis[l«maxn];intdp[l«maxn];intdfs(intstate){if(vis[state])returndp[state];vis[state]=1;for(inti=0;i<b;i++){if(state&intt=score[state八(l«i)]-score[state];elsedpfstate]=max(dp[state]zscore[0]-score[state]-)returndp[state];io)intmain(){inti,n,x,j,k;while(cin»g»b»s){if(g==0&&b==0&&s==0)break;for(i=0;i<b;i++)bg[i].clear();for(i=0;i<b;i++){sccinf("％cT,&n);while(n-){scantf'%d",&x);bg[i].push_back(x);}}n=l«b;for(i=0;i<n;i++){score[i]=0;memset(sum,0,sizeof(sum));for(j=0;j<b；j++){if((i&(1<|))==0){for(k=0;k<bg[j].size();k++)sum[bg[j][k]]++;))for(j=1;j<=g;j++)score[i]+=sum[j]/s;memset(vis,0,sizeof(vis));memset(dp,0,sizeof(dp));cout«2*dfs(n-l)-score[0]«endl;)return0;)题意：20之内的数字，每次可以选一个数字，然后它的倍数，还有其他己选数的倍数组合的数都不能再选，谁先不能选数谁就输了，问赢的方法constintN=1050005;intt,n,w,start,dp[N],ans[25]zan;intgetnext(intstate,intx){for(inti=x;i<=20;i+=x)if(state&(l«(i-2)))statea=(l«(i-2));for(inti=2;i<=20;i++){if(state&(l«(i-2))){for(intj=x;i-j>=2;j+=x){if(!(state&(l«(i-j-2)))){statea=(i«(i-2));break;))))returnstate;)intdfs(intstate){if(dp[state]!=-l)returndpfstate];if(state二二0)returndp[state]=0;for(inti=2;i<=20;i++){if(state&(l«(i-2)))(if(dfs(getnext(state,i))==0)returndp[state]=1;))returndp[state]=0;)intmain(){intcas=0;memset(dp,-1,sizeof(dp));scanf("%d",&t);while(t-){start=0;an=0;scanf("%d"z&n);for(inti=0;i<n;i++){scanf("%d"z&w);start|=(l«(w-2));for(inti=2;i<=20;i++){if(start&(l«(i-2))){if(dfs(getnext(startzi))==0)ans[an++]=i;)printf("Scenario#%d:\n,,,++cas);if(an){printf("Thewinningmovesare:");for(inti=0;i<an;i++)printf("%d"zans[i]);printf(".\n");)elseprin甘("Thereisnowinningmove.\n");printf(H\n");)return0;给你2n个人，两方各n个人，交叉坐，每个人可以取的石子有一个最大限制，总共有S颗石子，哪一方取了最后一颗石子就输了，问先取石子的这一方是否有必胜优^出占Oconstintmaxn=1«13+5;boolvis[maxn][22];intn;inta[22];intdp[maxn][22];intdfs(intsumzintid){if(vis[sum][id])returndp[sum][id];vis[sum][id]=1;if(sum==0)returndp[sum][id]=1;for(inti=1;i<=a[id]&&i<=sum；i++){if(dfs(sum-i,(id+1)%(2*n))==0)returndp[sum][id]=1;returndp[sum][id]=0;while(cin»n&&n){cin»s;for(i=0;i<2*n;i++)scanf("%d"z&a[i]);memset(vis,0,sizeof(vis));cout«dfs(s,0)«endl;return0;)题目大意：有一个数组，每次只能取第一个元素或者最后一个元素，两个人轮流取，问先手取能获得的最大值。这是题很明显的博弈类型的DP,由于每次只能取首尾的元素，可以采用经典的枚举长度DPDP[J][I][2]第一维表示当前长度，第二维表示起点，第三维0表示先手最优值，1表示后手最优值。由于两个人都是足够聪明，那么每次都会在当前状态取最优策略。转移方程：如果当前是先手取dpO][i][0]=max(dp[j-1][i+1][0]+a[i],dpO-1][i][0]+a[i+j-1 那么会选择最大值dp[j]皿后手的只能取小的了,因为大的被先手取了同理可得当前是后手取dp[j][i][0]=min(dp[j-1][i+1][0],dp[j-1][i][0]);dp[j][i][1]=max(dp0-1][i+1][1]+a[i],dp[j-1][i][1]+a[i+j-1]);因为状态是N*N*2=10A8,超出规定内存，改用滚动数组进行DP即可。源代码：constintmaxn=10001;LL dp[2][maxn][2],a[maxn];intmain(){inti,n,k;while(cin»n&&n){for(i=1;i<=n;i++){scanf(,,%lld,,z&a[i]);dp[l][i][l]=a[i]；dp[l][i][0]=0;)k=0;for(intlen=2;len<=n;len++){for(i=1;i+len-1v=n;i++){if(len%2==0){dp[k][i][0]=max(a[i]+dpg][i+l]⑼,a[i+len-l]+dp[kAi][i][0]);dp[k][i][l]=min(dp[kAi][i][i],dp[kAi][i+i][i])；else{dp[k][i][l]=max(a[i]+dp[kAl][i+l][l]za[i+len-1]+dp[kA]][i][l])；dp[k][i][0]=min(dp[ka1][i][0],dp[ka1][i+1][0]);_1k]；}cout«dp[kA]][l][0]«endl;一}_return0;)三堆石头，每次从一堆中取走若干，或者从两堆中取走相同的数量，最后取的人胜。booldp[maxn][maxn][maxn]voidDP(){memset(dp,0,sizeof(dp));inti,j,k,r;for(i=0;i<=300;i++){for(j=0;j<=300;j++){for(k=0;k<=300;k++){dp[i+r][j][k]if(dp[i][j][k])continue;

for(r=1;i+dp[i+r][j][k]for(r=1for(r=1j+r<=300;r++)dpfor(r=1for(r=1k+r<=300;r++)dp[i][j][k+r]for(r=for(r=for(r=for(r=1;i+r<=300&&j+r<=[i-dp][j+r][k]=1;1;i+r<=300&&k+r<=for(r[i加][j][k+r]1;j+r<=300

[i]dpj+r][k+r]=1；&&k+r<==1；300;r++)300;r++)300;r++)intmain(){DP();inta,brc;while(cin>>a>>b>>c)cout«dp[a][b][c]<<endl;return0;题意：给定一个日期，两个人轮流走，每次可以走一月或者一天，问最后谁能走到这个日子intmonthday[13]={0,31,28,31,30,31,30,31,31,30,31,30,31);intleap(inty){return((y%4==0)&&(y%100!=0))II(y%400==0);)structDay{inty,m,d;Day(){}Day(inty,intm,intd){this->y=y;this->m=m;this->d=d;intvalidintvalid(){//〈二2001,if(y>2001)returnif(y<2001)returnif(m>11)returnif(m==11&&d〉4)if(leap(y)&&m==2if(d>monthday[m])return1;11,40;1；0;return0;&&d==29)return1return0;friendbooloperator==friendbooloperator==returna.y==b.y&&(constDay&a,constDay&b){a.mb.m&&a.d==b.d;）；Daynextday(constDay&dy,intk){ //今天为(y,m,d)后k天的日期intmd,y=dy・yrm=dy.m,d=dy.d;for(inti=1;i<=k;i++){日;if(leap(y)&&m==2)md=monthday[m]+1;elsemd=monthday[m];if(d==md+1){1;++m;if(m==13){=ml;++y;)})returnDay(y,m,d) ;)Daynextmonth(constDay&dy){ //今天为(y,m,d)后-^月intmd,y=dy.y,m=dy.m,d=dy.d;m+;if(m>12){m-=12 ;y++;}returnDay(y,m,d) ;)boolvis[2005][13][32];intdp[2005][13][32];intdfs(Daydy){//printf(n%d%d%d\nn/dy.y/dy.m/dy.d);if(vis[dy.y][dy.m][dy.d])returndp[dy.y][dy.m][dy.d];vi^dy.y][dy.m][dy.d]=1;if(dy==Day(2001,11,4))returndp[dy.y][dy.m][dy.d]=0;Daynx=nextday(dy,1);if(nx.valid()){if(dfs(nx)==0)returndp[dy.y][dy.m][dy.d]=1 ;题意：有N个数，有一个区间[A,B],第一个人先取一个数，必须在区间内，后一次取必须比第一个数大，而且差值在区间内。问最后两个人取的数的和的差值最大为多少。constintmaxn=10008;constintinf=1000000000;intx[maxn];inta,b,n;intdp[maxn];intdfs(intid){if(dp[id]!=-inf)returndp[id];intt=inf;for(inti=id+1;i<=n;i++){if(x[i]-x[id]>=a&&x[i]-x[id]<=b){t=min(t,x[id]-dfs(i));})if(t==inf)dp[id]=x[id];else dp[id]=t;returndp[id];}intmain(){intt,i,ans;cin»t;while(t-){cin»n»a»b;for(i=1;i<=n;i++)scanf("%d",&x[i]);sort(x+l,x+l+n);for(i=1;i<=n;i++)dp[i]=-inf;ans=-inf;for(i=1;i<=n;i++){if(x[i]>=a&&x[i]<=b)ans=max(ans,dfs(i));}if(ans==-inf)printf("0\n");else printf("%d\n",ans);)return0;)nx=nextmonth(dy);if(nx.valid()){if(dfs(nx)==0)returndp[dy.y][dy.m][dy.d]=1 ;)returndpfdy.y][dy.m][dy.d]=0;}intmain(){memset(vis,0,sizeof(vis));intt;Daydy;cifc>t;while(t--){ci>n>dy.y>>dy.m>>dy.d;printf(H%s\nn,dfs(dy)?HYESH:HNOH);)return0;题目分析：九宫格，只利用九宫格的边。开始，边都没有添加。两个人轮流添加边，如果某人添加了某边之后，形成了x个新的1/1的方格，则此人得x分。边全部添加完后，得分高者获胜。已经进行到第n轮，问是先手赢，还是后手赢。Thereisa3by3gridandeachvertexisassignedanumber.Illi④,⑥■-④Illi④.⑥・⑥■•玲' 'I*ItlookslikeJiuGongGe,buttheyaredifferent,forwearenotgoingtofillthecellbuttheedge.Forinstance,R,o>-,t>-^-<3>-,R,o>-,t>-^-<3>-,⑦—©—^■----<4>—④—@—⑥addingedge6>10Theruleofthisgameisthateachplayertakesturnstoaddanedge.Youwillgetonepointiftheedgeyoujustadded,togetherwithedgesalreadyaddedbefore,formsanewsquare(onlysquareofsize1isconsidered).Ofcourse,yougettwopointsifthatedgeformstwosquares.Noticethatanedgecanbeaddedonlyonce.-—立12-—立12formingtwosquarestogettwopointsTom200andJerry404isplayingthislittlegame,andhaveplayednroundswhenFishheadcomesin.Fishheadwantstoknowwhowillbethewinner.Canyouhelphim?AssumethatTom200andJerry404arecleverenoughtomakeoptimaldecisionsineachround.EveryGamestartsfromTom200.ThefirstlineoftheinputcontainsasingleintegerT(T<=100),thenumberoftestcases.Foreachcase,thefirstlinecontainsanintegersn(12<=n<=24),whichmeanstheyhavetakentotalnroundsinturn.Nextnlineseachcontainstwointegersa5b(a?b<=16)representingthetwoendpointsoftheedge.ForeachcaseoutputonelinenCase#X:”，representingtheXthcase,startingfrom1.IfTom200wins,printnTom200Hononeline,print"Jerry404Hotherwise.structPoint{intx;inty;Point(){}Point(intajntb):x(a),y(b){}};booledge_row[5][5];booledge_col[5][5];booltom_turn;intedge_num;inttom_scorezjerry_score;Pointget_point(intx){returnPoint((x-1)/4z(x-1)%4);)voidadd_edge(Pointpl,Pointp2,boolvalue){if(pl.x>p2.x||pl.y>p2.y)swap(plzp2);if(pl.x==p2.x)edge_row[pl.x][pl.y]=value;elseedge_col[p1.x][p1,y]=value;)intsqure(Pointa){if(a.x<0||a.x>2||a.y<0||a.y>2)return0;boolr=true;r=r&&edge_row[a.x][a.y];r=r&&edge_row[a.x+l][a.y];r=r&&edge_col[a.x][a.y];r=r&&edge_col[a.x][a.y+1];if(r)return1;elsereturn0;)intget_score(Pointa/Pointb){if(a.x>b.x||a.y>b.y)swap(a,b);if(a.x==b.x)returnsqure(Point(a.x-1za.y))+squre(a);returnsqure(Point(a.xza.y-1))+squre(a);)voidinput(){tom_turn=true;tom_score=jerry_score=0;inti,a,b;scanf("%d"z&edge_num);memset(edge_row,0,sizeof(edge_row));memset(edge_col,0,sizeof(edge_col));for(i=0;i<edge_num;i++){scanf("%d%d"z&a,&b);Pointpl=get_point(a);Pointp2=get_point(b);odd_edge(pl,p2,true);if(tom_turn)tom_score+=get_score(plzp2);elsejerry_score+=get_score(pl,p2);tom_turn=!tom_turn;))booldfs(intnow,intpre,intturn){boolwin=false;booldid=false;for(inti=0;i<4;i++){for(intj=0;j<3;j++){if(!edge_row[i]U]){did=true;Pointa=Point(izj);Pointb=Point(i,j+1)；add_edge(azbztrue);ints=get_score(a,b);win=!dfs(pre,now+szIturn);add_edge(a,bzfalse);if(win)returntrue;)if(!edge_col[j][i]){did=true;Pointa=Point(jzi);Pointb=Point(j+1,i);add_edge(azbztrue);ints=get_score(a,b);win=!dfs(pre,now+s,Iturn);add_edge(a,b,false);if(win)returntrue;)))if(!did){if(now==pre)return!tom_turn;returnnow>pre;returnfalse;)intmain(){intCase;cin»Case;for(inti=1;i<=Case;i++){input();booltom_win;if(tom_turn)tom_win=dfs(tom_score,jerry_score,tom_turn);elsetomwin=!dfs(jerry_score,tom_score,!tom_turn);printf("Case#%d:"zi);if(tom_win)prin甘(Tom200\n”)；elseprintf("Jerry404\n");)return0;)Alice和Bob玩一个游戏，有两个长度为N的正整数数字序列，每次他们两个只能从其中一个序列，选择两端中的一个拿走。他们都希望可以拿到尽量大的数字之和，并且他们都足够聪明，每次都选择最优策略。Alice先选择，问最终Alice拿到的数字总和是多少？constintmaxn=25;constintinf=1000000000;inta[maxn]zb[maxn];intsa[maxn],sb[maxn];intdp[maxn][maxn][maxn][maxn];intdfs(intI,intr,intLzintR){if(l>r&&L>R)return0;if(dp[l][r][L][R]!=-l)returndp[l][r][L][R];dp[l][r][L][R]=0;intsum=sa[r]-sa[l-l]+sb[R]-sb[L-l];if(l<=r){dp[l][r][L][R]=max(sum-dfs(l+1,r,L,R),dp[I][r][L][R]);dp[l][r][L][R]=max(sum-dfs(l,r-1,L,R),dp[l][r][L][R]);)if(L<=R){dp[l][r][L][R]=max(sum-dfs(l,r,L+l,R),dp[l][r][L][R]);dp[l][r][L][R]=max(sum-dfs(l,rzL,R-1),dp[l][r][L][R]);)returndp[l][r][L][R];)intmain(){inttzizn;cin»t;while(t-){cin»n;sa[0]=0;for(i=1;i<=n;i++){scanf(n%dH,sa[i]=sa[i-l]+a[i];)sb[0]=0;for(i=1;i<=n;i++){scantf^d"&b[i]);sb[i]=sb[i-l]+b[i];)memset(dpz-1,sizeof(dp));cout«dfs(l,n,1,n)«endl;)return0;)两个公司从教育部轮流申请资金，如果库中钱充足的话那么就会拨给这个公司，如果一旦库中没有钱那么停止，如果申请的钱多余库中的那么教育部长会把手中的m元钱给他之后申请结束，开始库中有n元钱，每个公司每次申请资金的范围是[l,k],问先手的公司最多能得到多少钱，在得到最多钱的情况下能让对手得至撮少的钱数。题解：开始是博弈的想法，枚举每个人决策的平衡态，莫名其妙的过了，队友搞了dp,找到一组反例证明我的博弈想法是有错误的，dp应该是正解。dp[i][0]代表的是当前剩余i元钱先手申请到的最多的钱，dp[i][l]代表剩余i元钱先手得到的最多钱时对手得到的最少的钱，constintmaxn=22;intnzmzk;boolvis[10002][2