学步园

状压DP

状压DP这玩意儿说实话没什么总结的，不过还是要说说

既然是状压，那么就少不了位运算，所以位运算要熟悉

总结起来说，就是先把它写成二进制（8位），然后按下表规则进行运算

再说说一些实战中的小技巧把

比如【SCOI2005互不侵犯】一题中，放置一个国王后，它那一行内的左右不能再放，直白点就是每一行不能有相邻两个1出现

当然我们可以枚举每一种情况，然后判断是否有相邻的两个1，但是有时候情况就会很多，如【炮兵阵地POJ1185】，但是可行的情况却不多，所以我们可以先把每一行中可行的找出来

如何找呢？想到dfs没？这可是一个找所有方案的利器啊！

比如当n=4的时候，我们要找出0000,0001,0010,0100,0101,1000,1001,1010这些方案

具体怎么找就不说了，看看代码

主程序调用dfs(0,0)即可

然后就是写代码的一些技巧，动态规划出了可以写递推以外，还可以以记忆化的形式实现，比如说【棋盘游戏】一题（下面有链接），我考试的时候写递推就写昏了，但是改成记忆化，也就是dfs的形式，很轻松就写出来了

我做过的一些状压：

棋盘游戏 board

http://blog.csdn.net/jiangzh7/article/details/8592387

[SCOI2005]互不侵犯 king

http://blog.csdn.net/jiangzh7/article/details/8619644

Mondriaan's Dream POJ2411【基础状压】

http://blog.csdn.net/jiangzh7/article/details/8629641

炮兵阵地 POJ1185

http://blog.csdn.net/jiangzh7/article/details/8629872

售货员的难题【本来是搜索的】

http://blog.csdn.net/jiangzh7/article/details/8631048

Corn Fields POJ3254

http://blog.csdn.net/jiangzh7/article/details/8631768

扫雷 SCOI2005

http://blog.csdn.net/jiangzh7/article/details/8731992