ZOJ 4257 MostPowerful 状压DP

缘起

练习状压DP~

分析

1
2
不超过10种不同气体，两两之间相互碰撞可以产生一定的能量，如a碰b，那么b气体就消失，自身不能碰自身，问最后
所能得到的最大能量。

很遗憾, 本题在zoj上已经找不到了。这里只讲思路，就不再写代码了. 因为气体种数<=10, 很小, 所以自然想到状压DP. 用一个[0,full:= 1<<n)的整数刻画当前还剩下的气体种类. 剩下就是1, 不剩下就是0

其实能用状压DP的，一定是当前状态能达到的值仅仅依赖某个状态. 令dp[i] 为状态为i的时候，从i状态开始计0，能产生的最大能量，则显然答案是 dp[full-1], 即所有气体都剩下的时候能产生的最大能量. 则考虑dp[i]的状态转移. 因为n太小了, 所以显然可以枚举剩下的气体中的两种进行碰撞. 至多100种嘛情况嘛~ 而只需要取大即可.

本题属于简单状压DP。水题一枚~