team2012-D1-sol-0044

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

状态压缩dp, 好题! 一开始看这题, 感觉状态数很多, 2^12^ = 4096, 一般的想法是 1000*4096*4096*4096 的 dp. 这个根本不可能, 但是通过一次筛选后, 把 4096 个状态中所有存在两个连续 1 的状态都筛掉, 发现一共只有 466 个可用状态. 然后再枚举每种障碍摆放的 mask, 每一行最多只会有 150+ 的可行状态. 所以状态空间就缩的很小了. 再加上需要判掉相邻两行不互相攻击的状态, 这样 4096*4096 的状态数就减少到非常少了. 然后就写几个 check 函数判断一下作一下状态转移就好了, check 函数具体看我的代码吧, 很好懂.

状态压缩dp, 好题! 一开始看这题, 感觉状态数很多, 2¹² = 4096, 一般的想法是 1000*4096*4096*4096 的 dp. 这个根本不可能, 但是通过一次筛选后, 把 4096 个状态中所有存在两个连续 1 的状态都筛掉, 发现一共只有 466 个可用状态. 然后再枚举每种障碍摆放的 mask, 每一行最多只会有 150+ 的可行状态. 所以状态空间就缩的很小了. 再加上需要判掉相邻两行不互相攻击的状态, 这样 4096*4096 的状态数就减少到非常少了. 然后就写几个 check 函数判断一下作一下状态转移就好了, check 函数具体看我的代码吧, 很好懂.