状态压缩动态规划学习笔记

把标签和分类连在一起读就是标题了（

好像上一篇珂朵莉树学习笔记也是这样（

马上就要复赛了，但反正我已经退役预定了来颓 blog 吧。

首先我们来看一道例题，「USACO06NOV」玉米田 Corn Fields。

首先，我们想到定义 f[i][...] 表示当前处理到第 $i$ 行，然后 blablabla 一堆状态的总方案数。既然任意两块草地之间不能有公共边，我们肯定需要记录第 $i$ 行哪些地方种了草，哪些地方没种草。那么我们记录的状态就是……f[i][0/1]...( 省略 10 个[0/1])...[0/1]，后面 $12$ 维状态中第 $j+1$ 维表示的是第 $i$ 行第 $j$ 列是否种草。

但是等等……$13$ 维的状态……

注意到，后面 $12$ 维状态只有 $0$ 和 $1$，于是我们就有了这么一个想法：把后 $12$ 维状态看成一个 $2$ 进制数，其中从右往左第 $i$ 位表示当前行第 $i$ 列是否种草，$1$ 表示种，$0$ 表示不种。在这一过程中，我们将后 $12$ 维状态「压缩」成了一个 $2$ 进制数，这也正是「状态压缩」这个名字的含义。

于是，现在我们定义 f[i][S] 表示当前处理到第 $i$ 行，其中第 $i$ 行的状态是 $S$ 的总方案数。在转移时，我们还需要判断状态是否合法，我们可以定义 a[i] 表示第 $i$ 行哪些格子能种草，$1$ 表示能，$0$ 表示不能。valid[S] 表示如果不考虑某些格子不能种草，状态 $S$ 是否合法，也就是是否不存在两个相邻的 $1$。a[i] 在读入时就可以处理出来，至于 valid[S]，我们可以通过这样的一个循环处理出来：

for(re int i=1;i<(1<<m);++i)
 valid[i]=valid[i>>1]&(~(i&(i>>1)&1));

用人话来讲就是 [S 是否合法]=[S>>1 是否合法]&[S 与 S>>1 的最后一位是否不同为 1]。

在转移时，我们认为当前枚举到的状态是合法的当且仅当它只在能种草的格子上种草，并且不与上一行的状态冲突，也就是 (S|a[i])==a[i]&&valid[S]&&(S&S')==0。

for(re int i=0;i<(1<<m);++i)
 if((i|a[1])==a[1]&&valid[i])
 f[1][i]=1;
for(re int i=2;i<=n;++i)
 for(re int j=0;j<(1<<m);++j)
 if((j|a[i])==a[i]&&valid[j])
 for(re int k=0;k<(1<<m);++k)
 if((k|a[i-1])==a[i-1]&&valid[k]&&(k&j)==0)
 (f[i][j]+=f[i-1][k])%=mod;

粗略计算的话，时间复杂度差不多是 $O(n4^m)$，最坏情况下差不多是 $12\times 4^{12}=201326592$，看着很吓人，然而实际上，其中大部分状态都是不合法的，会被我们的两个 if 剪掉，因而实际运行跑得比谁都快（

为了更好地体会状压的复杂度的神奇之处，我们再来看一下这道题，「NOI2001」炮兵阵地。

因为一个炮兵部队的攻击范围能够上下扩展两行，我们在记录状态时，需要记录之前两行的状态，也就是用 f[i][S1][S2] 表示当前处理到第 $i$ 行，第 $i-1$ 行状态为 $S1$，第 $i$ 状态为 $S2$ 时最多能放多少个炮兵部队。我们自然也需要记录 a[i] 和 valid[S]，不过，这次 valid[s] 的预处理过程差不多是这样：

for(re int i=1;i<(1<<m);++i){
 valid[i]=(i&1)?valid[i>>3]&((~i)>>2)&((~i)>>1):valid[i>>1];

看起来有些非常复杂，用人话来讲就是……诶我当时是不是写错了（

……不好像又没写错……

好吧没写错。

如果 $S$ 的最后一位是 $1$，则 [S 是否合法]=[S>>3 是否合法]&[S 的倒数第 2 位和倒数第 3 位是否都为 0]，否则 [S 是否合法]=[S>>1 是否合法]。

因为我们要求的是最多能放多少个炮兵部队，我们还需要知道某个状态放了多少个炮兵部队，也就是某个状态 $S$ 在二进制下 $1$ 的个数，我们可以这样处理：

for(re int i=1;i<(1<<m);++i)
 cnt[i]=cnt[i>>1]+(i&1);

转移过程如下：

for(re int i=0;i<(1<<m);++i)
 if((i|a[1])==a[1]&&valid[i])
 for(re int j=0;j<(1<<m);++j)
 if((j|a[2])==a[2]&&valid[j]&&(i&j)==0)
 f[2][i][j]=cnt[i]+cnt[j];
for(re int i=3;i<=n;++i)
 for(re int j=0;j<(1<<m);++j)
 if((j|a[i-2])==a[i-2]&&valid[j])
 for(re int k=0;k<(1<<m);++k)
 if((k|a[i-1])==a[i-1]&&valid[k]&&(j&k)==0)
 for(re int l=0;l<(1<<m);++l)
 if((l|a[i])==a[i]&&valid[l]&&(l&j)==0&&(l&k)==0)
 f[i][k][l]=max(f[i][k][l],f[i-1][j][k]+cnt[l]);

时间复杂度差不多是 $O(n8^m)$，最坏情况下差不多是 $100\times 8^{10}=107374182400$，然而由于转移过程中的大量剪枝，实际时间复杂度差不多是 $O(\text{won’t TLE})$（

我们再来看一个状压的应用，「SP3953」MMINPAID - Paid Roads，或者您也可以反正我就是在洛谷 上提交。

大概是一道最短路，然而与一般的最短路不同的是，在这道题中，经过某条边之前所经过的节点集合如果不同，可能会导致花费的不同。这样一来，我们一般的最短路算法就会有后效性。解决方法也很简单，就是把经过节点集合压缩到一个 $2$ 进制数内。定义 dis[u][S] 为只经过 $S$ 内的节点的前提下，从 $1$ 到 $u$ 的最小花费。对于 $u$ 发出的所有边的终点 $v$，dis[v][S|(1<<(v-1))]=min(dis[v][S|(1<<(v-1))],dis[u][S]+cost)，其中 $cost$ 表示经过从 $u$ 到 $v$ 这条边的花费，当然这需要分情况讨论。

这样一来，我们只需要写一个可重复入队的堆优化 Dijkstra 就可以了。需要注意的是，我们需要把节点与经过节点集合看成是一个整体，或者说，将它们联系在一起然后抽象成一个「点」。

我是不会说我把 impossible 打成 Impossible 然后交上去 WA 了一发的（

一般情况下，如果一道题数据范围很小，但是爆搜过不去，比如说 $n\leqslant 20$，就很有可能是状压题或者也有可能是神仙剪枝题。大部分状压的时间复杂度都不会直接是一个 $O(2^n)$，$O(n2^n)$ 或者说 $O(n^22^n)$ 大概比较常见，当然我比较菜，做过的题比较少，所以这一段基本是瞎扯。

以上，我觉得我的状压讲的差不多了（