目录
状态压缩动态规划
就是对状态做一个压缩，一般是用二进制表示，比如
P1896 [SCOI2005] 互不侵犯
每一行的状态一般来说要开好多维数组，然而一个二进制就搞定了。
预处理：首先 1<<n 范围枚举状态，筛选出合法状态，记录每一个合法状态的点数。
设 \(f_{i,j,k}\) 表示前 i 行，放 j 个士兵，当前行的状态是 k 的方案数。初始化 \(f_{0,0,0}=1\)。
转移：
对于前i行，放j个士兵的情况，考虑转移。双重循环枚举状态，分别用a和b表示（a循环在外），用c记录a状态的士兵数。
进行判断：如果j不小于c；正对判断；错位判断（位运算的巧用）。如果都满足，则 \(f_{i,j,a}=f_{i-1,j-c,b}\)
具体见代码。
最后有一个技巧，多算一层，直接输出 \(f_{n+1,k,0}\) 就可以，虽说并没有节省时间复杂度。
P1879 [USACO06NOV] Corn Fields G
和上一个问题的区别就在于约束条件，变成了十字形的，另外还加了一个贫瘠土地的限制。
判断条件：!(s[a] & s[b]) && (s[a] & g[i]) == s[a]
第一个的意义是水平判断，和上题一样；第二个是障碍判断，位运算巧用。
滚动数组的另一种操作方法，用与运算来维护，每次更新 \(i\oplus 1\) 的位置就好。
P2704 [NOI2001] 炮兵阵地
十字形的约束扩大了一层。
\(f_{i,a,b}\) 表示前i行，第i行是状态a，第i-1行是状态b的方案数。
判断：
但这里面有一些冗余，删除之后：（因为比较状态合法只需要a-b,a-c之间合法，b-c就合法；另外，b这一层在a的上一层，b肯定已经被算过合法状态了，所以转移一定不会出现不合地图的情况，所以不用判断b的地图合法性）
转移：
\(f[i \& 1][a][b] = \max(f[i \& 1][a][b], f[(i - 1) \& 1][b][c] + num[s[a]])\)
将第一维压缩为两个位，与运算交替，可以通过此题。
一些习题
P2622 关灯问题II；PRZ
[能力提升综合题单Part4 动态规划2]
标签：状态,判断,复习,压缩,合法,动态,规划,第一阶段 From： https://www.cnblogs.com/CYLSY/p/18219165