首页 > 代码库 > [博弈dp] hdu 4778 Gems Fight
[博弈dp] hdu 4778 Gems Fight
给出g种颜色的宝石,然后有B个背包,S代表到时候每种颜色的宝石凑齐S个能变成一个魔法石
然后B行数输入,每个包里有哪些宝石
然后A,B轮流拿包,每个包只能拿一次,拿出包把宝石放地上。
如果能变成魔法石则拿走魔法石,下一次还这个人拿包,没变成则换人。
魔法石的个数就是获得分数,问两人最优的时候分差是多少。
思路:
只有21个包,状压dp。
然后发现不管顺序如何 最后构成的魔法石的个数是一定的。
然后在不同的二进制状态下,所剩在地面上的宝石是一定的。
那么就可以dp[i] 代表i这个状态下 先手取所获得的最多得分。
dp[(1<<B)-1] 则是先手的答案了
然后已知构成魔法石数sum
则答案就是 dp[(1<<B)-1]-(sum-dp[(1<<B)-1])
每次只要枚举取拿个包 然后保留最大值
代码:
[cpp] view plaincopy
- #include"cstdlib"
- #include"cstdio"
- #include"cstring"
- #include"cmath"
- #include"queue"
- #include"algorithm"
- #include"iostream"
- #define inf 99999999
- using namespace std;
- int bag[22][12],c[12];
- int dp[1<<22];
- int g,n,s;
- int dfs(int x,int sum,int used[])
- {
- if(x==0||sum==0) return 0;
- if(dp[x]!=inf) return dp[x];
- int ans=0,mark[12];
- memset(mark,0,sizeof(mark));
- for(int i=0; i<n; i++)
- {
- int pp=0;
- if(x&(1<<i))
- {
- int tep=x^(1<<i),cnt=0;
- for(int j=0; j<g; j++)
- {
- mark[j]=used[j]+bag[i][j];
- cnt+=mark[j]/s;
- mark[j]%=s;
- }
- if(cnt>0) pp=cnt+dfs(tep,sum-cnt,mark); //构成魔法石继续取
- else pp=sum-dfs(tep,sum,mark); //换人了 得到的就是别人剩下的
- ans=max(ans,pp);
- }
- }
- return dp[x]=ans;
- }
- int main()
- {
- while(scanf("%d%d%d",&g,&n,&s),(g+n+s))
- {
- memset(bag,0,sizeof(bag));
- memset(c,0,sizeof(c));
- for(int i=0; i<n; i++)
- {
- int x;
- scanf("%d",&x);
- while(x--)
- {
- int y;
- scanf("%d",&y);
- bag[i][y-1]++;
- c[y-1]++;
- }
- }
- int sum=0;
- for(int i=0; i<g; i++) sum+=c[i]/s; //统计能构成多少个魔法石
- for(int i=0; i<(1<<n); i++) dp[i]=inf;
- int used[12];
- memset(used,0,sizeof(used));
- int ans=dfs((1<<n)-1,sum,used);
- printf("%d\n",ans-(sum-ans));
- }
- return 0;
- }
[博弈dp] hdu 4778 Gems Fight
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。