首页 > 代码库 > hdu4778：状压dp+博弈
hdu4778：状压dp+博弈
题目大意：
有g种不同颜色的小球，b个袋子，每个袋子里面有若干个每种小球
两人轮流取袋子，当袋子里面的同色小球有s个时，会合并成一个魔法球，并被此次取袋子的人获得
成功获得魔法球的人可以再次取
求二者都进行最优策略之后两人所得魔法球个数差
分析：
博弈，数据很小，自然想到了可以搜索所有状态
然后从每一步的子状态中找到对当前人（这一步的先手）最有利的状态即可
直接搜索还是会超时的，于是想到用状态压缩一下，做记忆化搜索
然后其实就是一个状压dp了
通过某个状态对于先手的最优子状态进行转移。。
代码如下
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000typedef struct Node{ int a,b;}node;node dp[2097152];bool vi[2097152];int num[25][25];int p[8];int g,b,s,k,m,x;void dfs(int state,int turn){ if(state==(1<<b)-1) { dp[state].a=0; dp[state].b=0; return ; } if(vi[state]) { return ; } int ok; node t; node ans; ans.a=-1000000; ans.b=0; int pp[8]; memcpy(pp,p,sizeof(pp)); for(int i=0;i<b;i++) { t.a=0; t.b=0; ok=0; if(state&(1<<i)) continue; int st=state|(1<<i); //状态 for(int j=0;j<g;j++) { p[j]+=num[i][j]; ok+=p[j]/s; p[j]%=s; } int tur=ok?turn:!turn;//是否交换选手 dfs(st,tur); memcpy(p,pp,sizeof(pp)); t.a+=ok; if(tur==turn) //子状态的先手所要转移到的状态相同 { t.a+=dp[st].a; t.b+=dp[st].b; } else //选手交换了 { t.b+=dp[st].a; t.a+=dp[st].b; } if(t.a-t.b>ans.a-ans.b) { ans=t; } } vi[state]=1; dp[state]=ans; return ;}int main(){ while(scanf("%d%d%d",&g,&b,&s),g+b+s) { memset(num,0,sizeof(num)); for(int i=0;i<b;i++) { scanf("%d",&k); while(k--) { scanf("%d",&x); num[i][x-1]++; } } memset(p,0,sizeof(p)); memset(vi,0,sizeof(vi)); dfs(0,0); printf("%d\n",dp[0].a-dp[0].b); } return 0;}
hdu4778：状压dp+博弈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。