状压 dp

· · 个人记录

状态压缩 dp 简称状压 dp

状压 dp 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

——OI Wiki

那么，它能干嘛？

把状态压缩来转移方程。

为了压缩更充分，我们常常使用二进制和位运算，不仅可以减小数字，还可以用位运算减小常数。

查看日报了解更多：

[洛谷日报第79期]二进制与位运算

注意表格中的运算均在二进制下进行

常用符号 解释
& （与） 都 1 为 1，其余为 0
| （或） 都 0 为 0，其余为 1
~ （非） 按位取反
^ （异或） 不同为 1，其余为 0
<<（左移） 每一位向左移动 x 位
>>（右移） 每一位向右移动 x 位

P1896 [SCOI2005] 互不侵犯

题目描述

在 N\times N 的棋盘里面放 K 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。

1 \leq N \leq 9, 0 \leq K \leq N * N

UPD：为了不与循环变量名冲突，我把题目中 K 改为了 m

注意到国王的影响范围非常小，所以方案数可能很大，所以想和八皇后那样爆搜肯定是不行的。

状态设计

考虑状压，设 f[i][j][k] 表示考虑到第 i 行，这一行状态为 j，已经用了 k 个国王的合法方案数。所谓状压，就是把状态压到了 j 里。

那么 j 是怎么表示状态的？显然我们只关心这一行每个位置国王的有无，那么有表示为 1，没有表示为 0，就可以压成一个数，因为 N \leq 9，所以状态数不超过 2^{10}，空间可以承受。

预处理

我们会注意到其实有很多状态在一行里就是不合法的，比如两个国王挨着，那么我们就要把前面一格有国王的状态忽略（然后不用考虑后面，因为如果后面有，统计到后面时也会算出来的），那么我们进行预处理，把有用的状态存入 s[]，顺便统计出每个状态的国王数，方便下面处理，给出代码：

void init(){
    for(int i=0;i<(1<<n);i++){//先枚举所有状态
        if(i&(i<<1)) continue;//前面一格不能有国王 
        s[++cnt]=i;//记录编号-状态对应 
        int t=i;
        for(;t;t-=t&(-t))//用树状数组的lowbit假装高大上QWQ
            ++num[cnt];//统计这个状态的国王数
    }
}

这样我们就记录了所有有用状态，所以数组也可以对应开小。

要开到多小呢，我们拿 n=9 运行一下，输出 cnt，发现是... 89

说明第二维甚至可以不用开到三位数，就进一步节省了空间。 虽然在这题没啥软用

呃，我们还要计算它的初始情况，就是第一行的情况。

我们直接枚举每个状态，如果这个状态的国王数小于等于 K，就把方案数设为 1，否则为 0。

状态转移

首先最外层循环肯定记录行数，是从 2 循环到 n。

那后面怎么转移呢？

别忘了第二维是状态

那么我们第二层循环枚举本行的状态，试图计算 f[i][j][]。

会发现每行状态还和上一行有关，怎么办？暴力循环上一行的所有状态进行枚举。

会发现有很多状态又不合法了，把它们 continue 掉。

这里就要用到二进制的位运算了。

那我们可以初步写出以下代码：

    for(int i=2;i<=n;i++){//枚举行数 
        for(int j=1;j<=cnt;j++){//枚举本行状态 
            for(int k=1;k<=cnt;k++){//枚举上一行状态 
                if((s[j])&(s[k])) continue;//k在j正上方 
                if((s[j])&(s[k]<<1)) continue;//k在j右上角 
                if((s[j]<<1)&(s[k])) continue;//k在j左上角 

                    //...do something
            }
        }
    }

这里的判断还是很重要的，不太理解的可以选几个数字模拟一下。

排除完不合法状态后就可以进行转移，会发现还有一维 k 未枚举，那么枚举它进行转移，给出代码：

for(int p=0;p+num[j]<=m;p++){//这一行上面一共有p个国王 
    f[i][j][p+num[j]]+=f[i-1][k][p];//上一行(状态为k共有p个国王)转移到(状态为j共有p+num[j]个国王)的这一行 
}

一定要注意国王总数的上限，枚举每一种状态进行转移。

答案统计

根据定义：考虑前 i 行，状态 j，用了 k 个国王。

我们可以循环所有状态统计 \sum_{j=1}^{cnt}{f[n][j][m]}

完整代码

#include<bits/stdc++.h>
using namespace std;
static char buf[1000001],*p1=buf,*p2=buf;//加在快读前面会加速快读，不用管
#ifdef ONLINE_JUDGE
    #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#endif
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
const int N=10; 
int n=read(),m=read();
long long f[N][100][N*N],sum;

int num[100],s[100],cnt;
void init(){
    for(int i=0;i<(1<<n);i++){
        if(i&(i<<1)) continue;//前面不能有国王 
        s[++cnt]=i;//记录编号-状态对应 
        int t=i;
        for(;t;t-=t&(-t))
            ++num[cnt];
    }
}

int main() {    
    init();
    for(int i=1;i<=cnt;i++)
        if(num[i]<=m) f[1][i][num[i]]=1;//预处理第1行 
    for(int i=2;i<=n;i++){//枚举行数 
        for(int j=1;j<=cnt;j++){//枚举本行状态 
            for(int k=1;k<=cnt;k++){//枚举上一行状态 
                if((s[j])&(s[k])) continue;//k在j正上方 
                if((s[j])&(s[k]<<1)) continue;//k在j右上角 
                if((s[j]<<1)&(s[k])) continue;//k在j左上角 
                for(int p=0;p+num[j]<=m;p++){//这一行上面一共有p个国王 
                    f[i][j][p+num[j]]+=f[i-1][k][p];//上一行(状态为k共有p个国王)转移到(状态为j共有p+num[j]个国王)的这一行 
                }
            }
        }
    }

    sum=0;
    for(int j=1;j<=cnt;j++)
        sum+=f[n][j][m];
    printf("%lld\n",sum);
    return 0;
}

P2704 [NOI2001] 炮兵阵地

题目描述

一个 N\times M 的地图由 N 行 M 列组成，地图的每一格可能是山地（用 \texttt{H} 表示），也可能是平原（用 \texttt{P} 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

对于 100\% 的数据，N\le 100，M\le 10，保证字符仅包含 P 与 H。

看到 M\leq 10 就知道状压应该可以。

会发现每一行部署只和这些有关：

那么我们状压就要压两个状态，再加上一个行数，那么定义 f[i][j][k] 为第 i 行上一行状态位 j 本行状态为 k 的最大炮兵数，这样可以枚举上上上行来进行转移，只不过空间好像有点吃紧，大概... 10^8 级别？

这怎么行！我们考虑减少空间，在这题有两种办法：

这里使用第二种

为什么不都弄？主要是不想再写了

那么还是利用预处理的优化，只记录有用状态并记录信息：

void init(){
    for(int i=0;i<(1<<m);i++){
        if((i&(i<<1))|(i&(i<<2))) continue;//注意这里两个都不能放
        s[++cnt]=i;
        int t=i;
        for(;t;t-=t&(-t))//诶嘿嘿
            ++num[cnt];
    }
}

啊这次我们就要预处理两行了，先处理第一行

其中 s[i] 存的是第 i 行的地图，P 为 1。

那么当状态有 1 在 H 上时（不合法），两数与的结果肯定会变小。

如果所有 1 都在 P 上（合法），两数与的结果肯定还是状态的值。

那么我们就能写出简洁的代码了：

for(int i=1;i<=cnt;i++)
    if((a[1]&s[i])==s[i]) f[1][0][i]=num[i];

第二行多一层循环枚举状态，而且注意不能在两行不能有炮在同一列

    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=cnt;j++){
            int x=s[i],y=s[j];
            if(x&y) continue;//同一列
            if((a[1]&x)!=x) continue;//第一行有建山上的
            if((a[2]&y)!=y) continue;//第二行有建山上的
            f[2][i][j]=f[1][0][i]+num[j];//状态转移
        }

还是有四层循环，第一层是行数，第二层是本行状态，第三层是上一行状态，第四层是上上行状态。

核心思想是利用上上行和上一行计算出上一行和本行的值。

相信你如果理解了看起代码应该不难：

    for(int i=3;i<=n;i++)
        for(int j=1;j<=cnt;j++){//本行 
            int x=s[j];
            if((a[i]&x)!=x) continue;//第i行的合法性 
            for(int k=1;k<=cnt;k++){//上一行 
                int y=s[k];
                if(x&y) continue;//本行和上一行不在同一列 
                if((a[i-1]&y)!=y) continue;//上一行的合法性 
                for(int p=1;p<=cnt;p++){//上上行 
                    int z=s[p];
                    if((x&z)|(y&z)) continue;//上上行不和上一行货本行在同一列
                    //这里就不判此行不合法了，反正是0 
                    f[i][k][j]=max(f[i][k][j],f[i-1][p][k]+num[j]);//状态转移 
                }
            }
        }

统计答案就让第一项为 n，枚举所有后面的状态取大的就好了。

然后我就开心的提交了，然后就100分了

就在我百思不得其解时我翻看了讨论区就进行思考。

从 100分 看出代码大体正确性可以保证，但被叉掉了说明在一些玄妙的边界会出错，从这个点跑的时间异常的小我们可以看出它并不大，肯定被小数据叉掉，那应该是小的边界...等等，小的边界？我看看代码：

if((a[1]&s[i])==s[i]) f[1][0][i]=num[i];

for(int i=1;i<=cnt;i++)
        for(int j=1;j<=cnt;j++)
            sum=max(sum,f[n][i][j]);

（微笑中透露着疲惫）

n=1 时炸了，它会输出 0

当然这里可以特判，但我发现我手贱——全是 0 的状态其实是在状态 1 的！

然后把所有 f[1][0][i] 改为 f[1][1][i] 即可。

完整代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
const int N=101;
const int M=11;
const int Z=65;
int n=read(),m=read(); 
int a[N];

long long f[N][Z][Z],sum;
int num[Z],s[Z],cnt;
void init(){
    for(int i=0;i<(1<<m);i++){
        if((i&(i<<1))|(i&(i<<2))) continue;
        s[++cnt]=i;
        int t=i;
        for(;t;t-=t&(-t))
            ++num[cnt];
    }
}

int main() {
    for(int i=1;i<=n;i++){
        char s[M];
        scanf(" %s",s+1);
        for(int j=1;j<=m;j++){
            a[i]|=(s[j]=='P')*(1<<(j-1));
        }
    }
    init();
    for(int i=1;i<=cnt;i++)
        if((a[1]&s[i])==s[i]) f[1][1][i]=num[i];
    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=cnt;j++){
            int x=s[i],y=s[j];
            if(x&y) continue;
            if((a[1]&x)!=x) continue;
            if((a[2]&y)!=y) continue;
            f[2][i][j]=f[1][1][i]+num[j];
        }
    for(int i=3;i<=n;i++)
        for(int j=1;j<=cnt;j++){
            int x=s[j];
            if((a[i]&x)!=x) continue;
            for(int k=1;k<=cnt;k++){
                int y=s[k];
                if(x&y) continue;
                if((a[i-1]&y)!=y) continue;
                for(int p=1;p<=cnt;p++){
                    int z=s[p];
                    if((x&z)|(y&z)) continue;
                    f[i][k][j]=max(f[i][k][j],f[i-1][p][k]+num[j]);
                }
            }
        }

    for(int i=1;i<=cnt;i++)
        for(int j=1;j<=cnt;j++)
            sum=max(sum,f[n][i][j]);
    printf("%lld\n",sum);
    return 0;
}