KeyDungeonDiv1
作者：洪华敦
关键词：贪心，动态规划
题目简述
有 n 扇门，每扇门开启需要红色钥匙 R[i] 把，绿色钥匙 G[i] 把，开启后可以获得红色钥匙 DR[i] 把，绿色钥匙 DG[i] 把，白色钥匙 DW[i] 把。
一开始你拥有一定数量的各种颜色的钥匙。
每扇门最多开一次，白色钥匙是万能钥匙，可以充当任何颜色的钥匙。
你的目标是，最大化你手中的钥匙总数，注意你不需要把门全部开完。
数据范围
1<=n<=12
0<=G[i]，R[i]，DR[i]，DG[i]，DW[i]<=10
题解
算法一
我们令 f[S][R][G][W] 表示开的门的集合为 S，钥匙数为 R，G，W 的方案是否存在。
转移时枚举下一扇门，计算开门后和拿钥匙后新的钥匙数量。
时间复杂度：。
算法二
算法一跑的太慢了，考虑优化他。
我们发现我们的这个 dp 方程是判定性的，考虑把方程转化成最优化的。
令 f[S][R][G] 表示开的门的集合为 S，钥匙数为 R，G 时白色钥匙最多有几把。
这样我们转移时，肯定是尽量不用白色钥匙，毕竟白色钥匙是万能的。
进一步的，我们可以发现，G 其实是可以由 R 和 W 推过来的。
于是只要令 f[S][R] 表示开的门的集合为 S，钥匙数为 R 时白色钥匙最多有几把即可。
时间复杂度