HDU 4778 Gems Fight! 解题报告

发布时间:2014-10-23 23:22:52
来源:分享查询网

题目 题意: 有一些背包,每个包里有一些宝石,A和B两人轮流操作,每次可以选一个包,将里面的宝石都放到公用坩埚里。如果坩埚里有某种颜色宝石的数目不少于s个,那么每s个这种颜色的宝石可以变成一个魔法石。如果操作者选完包后能得到魔法石,则他可以再操作一次。每个人都是最优策略(宝石尽可能比对方多),且可操作的时候必须操作,求A最多可以比B多多少魔法石。 题解: 可以用状压来做,i为哪些包选了,j表示操作者是谁,dp[i][j]表示操作完后A比B最多多多少宝石,显然如果j表示A的时候dp[i][j]越大越好,否则越小越好。计算dp[i][j]时,可知当前公用坩埚里还有什么宝石,然后枚举选择哪个包,选择结果最优的那个。

返回顶部
查看电脑版