状态压缩动态规划——状压dp

状压dp：意思是将状态进行压缩，从而更容易地写出状态转移方程

通常做法：将每个状态（一个集合）用二进制表示，每个位的1就代表着这个编号的元素存在，0就代表着这个编号的元素不存在，如二进制100110，即是集合{1,2,5}的压缩

通过状态压缩，我们可以使得状态通过位运算来判断是否可以转移

如：

一、

假设棋盘要放置k个国王，国王对其周围八个格子都可发动进攻，如果要求这一行与上一行的国王不能相互进攻

那么设上一行的状态为x（二进制数），这一行的状态为y的话，由于这一行放的国王的左上角，正上方，右上角都不能出现上一行的国王

所以：

正上方不出现上一行的国王的条件为：x&y==false

左上角不出现上一行的国王的条件为：x&(y<<1)==false

右上角不出现上一行的国王的条件为：x&(y>>1)==false

通过简单的位运算判断，对于每一个y，我们都可以枚举所有x，并可以快速找出能够转移到y的合法的x的状态，从而使状态转移变得简单

因此，对于这种题目，我们通常需要预处理出所有的x状态，以方便我们进行枚举

题目链接：#2153. 「SCOI2005」互不侵犯 - 题目 - LibreOJ (loj.ac)

实现代码：

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n,K;
int sti[600],sta[600],cnt;
//sti[i]：第i种状态压缩
//sta[i]: 第i种状态放的国王的数量
//cnt:状态总数
long long f[10][85][600];
//状态转移方程：
//f[i][l][j]:摆到第i行，已经摆了l个，而且第i行的摆法是j状态，总共有多少种方法数
//所以:
//f[i][l][j]=sigma f[i-1][l-sta[j]][x] 枚举所有合法的x//预处理所有状态
void dfs(int x,int num,int cur){if(cur>=n){sti[++cnt]=x;sta[cnt]=num;return;}dfs(x|(1<<cur),num+1,cur+2);//cur所指的位置放棋子，那么由于国王会进攻隔壁的棋子，所以cur+2才是到下一个能放棋子的位置dfs(x,num,cur+1);//cur所指的位置不放棋子，则遍历到下一个位置即可
}
int main(){cin>>n>>K;dfs(0,0,0);//先初始化第一行for(int i=1;i<=cnt;i++) f[1][sta[i]][i]=1;for(int i=2;i<=n;i++)//遍历到第i行for(int j=1;j<=cnt;j++)//第i行以第j种状态存在for(int k=K;k>=sta[j];k--)//枚举棋盘上已经摆了k个棋子for(int x=1;x<=cnt;x++)//枚举上一行所有要转移的状态xif(!(sti[j]&sti[x])&&!((sti[j]<<1)&sti[x])&&!((sti[j]>>1)&sti[x]))//判断是否合法f[i][k][j]+=f[i-1][k-sta[j]][x];long long sum=0;for(int j=1;j<=cnt;j++)sum+=f[n][K][j];cout<<sum;return 0;
}

两道练习题：

1.#10173. 「一本通 5.4 练习 2」炮兵阵地 - 题目 - LibreOJ (loj.ac)

实现代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,cnt;
int sti[2100],sta[2100];
//滚动数组
int f[2][2100][2100];
//预处理行
char s[100];
void dfs(int x,int num,int cur){if(cur>=m){sti[++cnt]=x;sta[cnt]=num;return;}dfs(x|(1<<cur),num+1,cur+3);dfs(x,num,cur+1);
}
int board[110];
int main(){cin>>n>>m;for(int i=1;i<=n;i++){scanf("%s",s);for(int j=0;j<m;j++) if(s[j]=='H') board[i]|=(1<<j);}dfs(0,0,0);for(int i=1;i<=cnt;i++) if(!(sti[i]&board[2])) for(int j=1;j<=cnt;j++) if(!(sti[j]&board[1])&&!(sti[i]&sti[j])) f[0][i][j]=sta[i]+sta[j];for(int i=3;i<=n;i++)for(int j=1;j<=cnt;j++)for(int x=1;x<=cnt;x++){f[i%2][j][x]=0;if(!(sti[j]&board[i])&&!(sti[x]&board[i-1])&&!(sti[j]&sti[x]))for(int k=1;k<=cnt;k++)if(!(sti[k]&board[i-2])&&!(sti[j]&sti[k])&&!(sti[x]&sti[k]))f[i%2][j][x]=max(f[i%2][j][x],f[(i%2)^1][x][k]+sta[j]);}int ans = 0;if(n==1){for(int i=1;i<=cnt;i++)if(!(board[1]&sti[i]))ans=max(ans,sta[i]);cout<<ans;return 0;}for(int i=1;i<=cnt;i++)for(int j=1;j<=cnt;j++)ans=max(ans,f[n%2][i][j]);cout<<ans;return 0;
}

2.P1879 [USACO06NOV] Corn Fields G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

实现代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
const int N = 5E3 + 10;
int cnt;
int board[13];
int sti[N];
long long f[13][N]; // f[i][j]：到了第i行，第i行为第j种状态的草坪
int mod = 1E8;
// 转移方程：
// f[i][j]=sigma f[i-1][x]
void dfs(int x, int cur)
{if (cur >= n){sti[++cnt] = x;return;}dfs(x | (1 << cur), cur + 2);dfs(x, cur + 1);
}
int main()
{cin >> m >> n;for (int i = 1; i <= m; i++){for (int j = 0, k; j < n; j++){scanf("%d", &k);board[i] |= ((k ^ 1) << j);}}dfs(0, 0);for (int i = 1; i <= cnt; i++)if (!(sti[i] & board[1]))f[1][i] = 1;for (int i = 2; i <= m; i++)for (int j = 1; j <= cnt; j++)for (int x = 1; x <= cnt; x++)if (!(sti[j] & sti[x]) && !(sti[j] & board[i]))f[i][j] = (f[i][j] + f[i - 1][x]) % mod;long long ans = 0;for (int i = 1; i <= cnt; i++)ans = (ans + f[m][i]) % mod;cout << ans;return 0;
}

二、

集合问题：

上文提到，用二进制对应位置的1，可表示该编号的元素存在于集合中，那么每一个二进制数就可以代表一个状态压缩的集合

我们先来熟悉以下几种位运算操作：

1.对于一个数x而言，x-1的二进制表达与x的区别在于，x-1将x的最低位的1变为了0，且这个1往后的更低位的0全都变为了1

那么如果我们进行x&(x-1)的操作，以x最低位的1为分界点，其往低位（包括其自身）都将变为0，而其更高位的x所对应的1保持不变，也就是说，如果我们进行x&(x-1)而得到的新的二进制数，实际上是把x的最低位的1变为0，其他保持不变所得到的新的二进制数

2.对于一个数而言，如果他是2的非负整数幂，它的二进制表达中一定只有一个1，且会在某个位置

由上述的x&(x-1)的操作我们可知，如果x是2的非负整数幂，那么一定有x&(x-1)==0

3.对于一个数x所代表的集合而言， 我们可通过消除其二进制表达的若干个1，从而得到他的全部子集，实现代码如下：

for(int s=m;s;s=(s-1)&m){
}

每进行一次迭代，都会得到一个s，s为m的一个非空子集的状态压缩

4.遍历元素个数为n的集合的子集的子集：

实现代码如下：

for(int m=0;m<(1<<n);m++){//第一个for遍历元素为n的集合的子集for(int s=m;s;s=(s-1)&m){//第二个for遍历子集的子集}
}

该操作的时间复杂度为，证明略

5.求集合a对全集u的补集b

则b=a^u

6.求集合a对全集u的交集b

则b=a&u

7.求集合a对全集u的并集b

则b=a|u

例题：

P5911 [POI2004] PRZ - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

实现代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int W,n;
int t[20],w[20],tim[70000];
const int INF=(1<<30);
//总共16个人
//记录所有合法子集的状态
//那么dp[i]表示状态为i的情况下，所用时的最短时间
//最后一定是求状态为全满的的dp值
//那么转移方程为：
//dp[i]=min(dp[a]+dp[b]),其中a|b==i
//也就是说a是i的全部子集
//那么b就是a对于i的补集
void check(int tmp,int total,int cost){for (int i = 0; i < n; i++){if ((tmp >> i) & 1){cost = min(cost, t[i]);total += w[i];}if(total>W) return;}tim[tmp]=cost;
}
int main(){cin>>W>>n;for(int i=0;i<n;i++) cin>>t[i]>>w[i];int N=(1<<n)-1;for(int m=N;m;m=(m-1)&N){tim[m]=INF;check(m,0,INF);}for(int m=0;m<(1<<n);m++)for(int s=m;s;s=(s-1)&m)tim[m]=min(tim[m],tim[s]+tim[m^s]);cout<<tim[N];return 0;
}