状态压缩 DP
状态压缩 DP
这种 DP 没有什么特殊的地方，在考虑问题的时候仍然像以前一样去考虑，但是当你注意到题中有一个特别小的数字的时候，或者你发现不能很好地设计状态的时候，你就可以考虑状态压缩。当然有时候可以考虑直接搜索后优化。
所谓状态压缩，就是将 DP 状态全部记录下来，一般采用二进制，即每一位都是一个独立的状态，代表某个东西的有无之类。
【引入】P1879 [USACO06NOV]Corn Fields G：题意如下。
农场主
\rm John 新买了一块长方形的新牧场，这块牧场被划分成M 行N 列(1 \le M \le 12, 1 \le N \le 12) ，每一格都是一块正方形的土地。\rm John 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是
\rm John 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
观察一下，数据范围非常小，而我们假如把行作为阶段，想从上一行转移到这一行来，势必要知道一行中所有的位置的情况。而我们就可以使用状压来表示每一行中草地的选取情况。不妨设二进制从低到高第
于是我们可以设计出状态：
我们不妨来计算一下这样写的复杂度，为
注意到我们每次都在判断是否可行，尤其是行内的判断，浪费了我们很多时间，而这些行的情况已经给出，我们为什么不预处理呢？具体的，我们首先暴力枚举每一行的每一个情况，把合法的存下来，转移的时候只枚举合法的，这样只需要一次判断（上下行）。
参考代码：
int n,m,a[N][N],f[N][M];
vector<int> s[N];
int ck(int x){
int lst = 0;
while(x){
if(lst&&(x&1)) return 0;
lst = x&1; x>>=1;
}return 1;
}
int ck(int x,int y){
F(i,1,m){
if(x%2==y%2&&x%2==1) return 0;
x/=2; y/=2;
}return 1;
}
void solve(){
n = rd();m = rd();
F(i,1,n){
int st = 0;
F(j,1,m) st = st * 2 + !rd();
for(int j=0;j<(1<<m);j++){
if((j&st)!=0||!ck(j))continue;
s[i].push_back(j);
}
}
for(int j:s[1]) f[1][j] = 1;
F(i,2,n)
for(int j:s[i])
for(int k:s[i-1])
if(ck(j,k))
f[i][j]+=f[i-1][k];
int ans = 0;
for(int j:s[n]) ans=(ans+f[n][j])%mod;
cout<<ans<<endl;
}当然，我写的代码还算是比较直观的，也偏长一点，对于位运算运用得当的高手而言，代码是很简单的。
我们再看两个非常经典的题。
【例题 1】P2704 [NOI2001] 炮兵阵地：
一个
N\times M 的地图由N 行M 列组成，地图的每一格可能是山地（用\texttt{H} 表示），也可能是平原（用\texttt{P} 表示），如下图。\texttt{P} 的位置可以放兵，攻击范围如图所示，不受地形影响。
求不误伤队友的前提下能放的兵最多有几个。
1\le N\le 100，1\le M\le 10
考虑状压。因为炮兵的攻击范围有点大，想当然我们的 DP 状态也需要多记录几行。
总体思路是一样的：
- 处理出行内的合法情况。
- 判断不同行之间的情况是否合法。
- 根据朴素的动态规划进行转移。
【例题 2】P1896 [SCOI2005] 互不侵犯：
和上一题几乎一样，只是把攻击范围稍加调整，思路不变。建议读者自行思考。
上面的几题都是裸的状压 DP，下面介绍几个经典的应用。
【例题 3】P3092 [USACO13NOV] No Change G：
约翰到商场购物，他的钱包里有
(1 \le K \le 16) 个硬币，他想按顺序买N 个物品(1 \le N \le 10^5) ，第i 个物品需要花费(1 \le c_i \le 10^4) 块钱。在依次进行的购买N个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。
请计算出在购买完
N 个物品后，约翰最多剩下多少钱。如果无法完成购买，输出-1 。