4228专题

BOJ 4228 哈哈哈

题目链接~~> 做题感悟:这题一看就知道要用状态压缩,本题和HDU 1429 胜利大逃亡(续)差不多。 解题思路:你可以把宝物压缩为二进制,例如:01001 代表你已经拿过 1 号和 4 号宝物了 0 代表相应的宝物没拿。用同样的方法把拿某个物品的前提条件也映射成二进制。假如你现在遇到 3 号宝物,如果3号宝物的前提条件是拿到 1 号 和 4 号宝物才能拿 3 号,那么前提条件可以用二进制表示