MagicalHats
作者：辜俊儒
关键词：状压dp
题目简述
给出一个 的地图，表示空地，表示帽子；
一开始玩家B将硬币放在帽子下面，每个帽子最多放一个硬币，每个硬币有一个价值；
玩家A有次机会，每次选择一个帽子，在翻开之前，玩家B可以随意改变硬币的位置，需要满足每一行的硬币数量加上帽子数量的和为偶数，每一列的硬币数量加上帽子数量的和为偶数。
问在玩家A和B的表现最佳的情况下，玩家A翻开的帽子中的所有硬币价值之和最大是多少。
地图中帽子数量，硬币数量均;
分析
由于帽子的个数有，可以考虑对帽子进行状压。
算法
用表示在状态下能获得的最大硬币数量。
第位为：第个帽子没有被翻开；
第位为：第个帽子被翻开后没有硬币；
第位为：第个帽子被翻开后有硬币；
转移：枚举一个没有被翻开的帽子（玩家A表现最佳，取最大值），考虑该帽子处是否需要留有硬币（玩家B表现最佳，取最小值）。
{ }
时间复杂度