状态压缩总结
内容
状态压缩是DP的一中神奇的方法。涉及到了非常有趣的二进制思想。
引言
在生活中我们经常接触一些和善的P问题，他们有O(1),O(log(n)),O(n^a)等多项式级的复杂度的问题，因为它的规模n出现在底数的位置；
当然还有一些恐怖的NPC问题，他们就是噩梦，因为他们的算法没有多项式级的解法，只有O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。
但是有没有好的解决方法呢，当然有，那就是——状态压缩
现在要普及一些基础知识（当然你也可以看 位运算技巧
（来自网络
更实用的技巧
如果要获得第i位的数据，判断((data&(1<<i-1))==0),若真，为0，假，为1； （把1移到i-1的位置，用&判断一下）
如果要设置第i位为1，data=(data|(1<<i-1)); （把1移到i-1的位置，加上data）
如果要设置第i位为0，data=(data&(~(1<<i-1))); （把1移到i-1的位置，取反，&一下）
如果要将第i位取反，data=(data^(1<<i-1)); （把1移到i-1的位置，异或一下）
如果要取出一个数的最后一个1(lowbit)：(data&(-data)) （这里利用的是负数取反加1实际上改变的是二进制最低位的1这个性质）
注意：
位运算的运算优先级非常低，位运算时一定要加括号
在写状压的时候，有一个很好用的工具
就是它
程序员模式
Lsh 是左移 Rsh 是右移 RoL 是右移1 RoR 是左移1
正文
例1
第一个例子并不是状态压缩
它是一个搜索
拯救公主
样例输入
1 7 8 2 ........ ..S..#0. .##..1.. .0#..... ...1#... ...##E.. ...1....
样例输出
11
这题是loli让我们刷搜索的时候意外找到的题。
求最短当然是广搜。广搜需要记录走过的位置以防重复（假如不想T死），可是不止记录坐标，也要记录收集了多少宝石。于是我们在广搜里加入一个状态表示每个宝石是否已经收集到了，如果收集到了新的宝石，那么先前不能vis的就可以重复走了。
问题在于怎么表示宝石的状态？观察数据范围，最多4个宝石。
压缩成二进制，可以有效解决。用这一位是1表示这个宝石收集过，用0表示这位宝石没有拿到，走到终点时判断有几个1即可。
这是一道很好的入门题，值得一做
一定要注意细节
代码
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#define N 210
using namespace std;
int dir[2][4]={{1,0,0,-1},{0,1,-1,0}};
int dp[N][N][1<<5-1],trans[20][2],n,m,k,tot,num,T,x,y,ans;
char map[N][N];
struct node{int x,y,step,key;node(int xx,int yy,int ss,int kk):x(xx),y(yy),step(ss),key(kk){};};
bool check(int key)
{
int cnt=0;
for(int i=0;i<=5;i++)
if((key>>i)&1)cnt++;
if(cnt>=k) return 1;
return 0;
}
int bfs(int x,int y)
{
queue<node>que;
dp[x][y][0]=1;
node now(x,y,0,0);
que.push(now);
while(!que.empty())
{
now=que.front();que.pop();
for (int i=0;i<4;i++)
{
int xx=now.x+dir[0][i],yy=now.y+dir[1][i],step=now.step,key=now.key;
if (xx<0 || xx>=n || yy<0 || yy>=m) continue;
if (dp[xx][yy][key]) continue;
if (map[xx][yy]=='#') continue;
if (map[xx][yy]=='E' && check(key)) return step+1;
if (isdigit(map[xx][yy])) dp[xx][yy][key]=1,key=key|(1<<(map[xx][yy]-'0')),que.push(node(xx,yy,step+1,key));
if (map[xx][yy]=='.') dp[xx][yy][key]=1,que.push(node(xx,yy,step+1,key));
if (map[xx][yy]=='$')
{
dp[xx][yy][key]=1,que.push(node(xx,yy,step+1,key));
for (int j=1;j<=tot;j++)
{
xx=trans[j][0],yy=trans[j][1];
if (!dp[xx][yy][key]) dp[xx][yy][key]=1,que.push(node(xx,yy,step+1,key));
}
}
}
}
return -1;
}
main()
{
cin>>T;
while(T--)
{
memset(dp,0,sizeof(dp));
tot=0;
num=0;
//scanf("%d%d%d",&n,&m,&k);
cin>>n>>m>>k;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
{
cin>>map[i][j];
if (map[i][j]=='S') x=i,y=j,map[i][j]='.';
if (map[i][j]=='$') trans[++tot][0]=i,trans[tot][1]=j;
if (isdigit(map[i][j])) num++;
}
if (k>num) {printf("oop!n"); continue;}
ans=bfs(x,y);
if (ans==-1) printf("oop!n");
else printf("%dn",ans);
}
}
选做题
符号三角形
样例输入
15 16 19 20 0
样例输出
15 1896 16 5160 19 32757 20 59984
这题是一道打表题= = 但是通过非常蛋疼的状压优化完全可以不代表做出来
具体见注释
#include <iostream>
using namespace std;
#define DEPTH 24
#define HALF 12
const int MASK = (1<<HALF) - 1;
/* 所有中间结果（即以某种加减号的组合开头的三角形共有几个负号）都存储在tag[]里。
虽然24层的三角形至多可能有 (1 + 24) * 24/2 = 300 个符号，但其中负号的数目根本达不到这么多，因为相邻的负号会导致下一行对应位置出现正号
实验证明24层的三角形中负号最多只有184个，因此可以用unsigned char存储，不会溢出！
存储方法是一层一层的堆式存储，delta1和delta2是两个指针，用来划分相邻两层
它们分别指示第d-1层和第d层所在存储区偏离tag[0]的位置 */
unsigned char tag[1<<DEPTH]={0};
unsigned delta1 = 0, delta2 = 1;
int cnt[DEPTH+2]={0};
char nneg[1<<HALF] = {0}; //nneg[i]表示i的二进制表示中有几个1(也即几个负号。0对应正号，1对应负号)
/*
递归计算：枚举深度为d的情形的第一行可能的值（共2^d种），再把第一行负号的数目与深度为d-1时负号的数目（已经算出，并保存在数组里）加起来，
从而得到深度为d时的全部结果。同时保存这些结果，以便后面深度为d+1时使用。
*/
void ID(int d)
{
unsigned i, j, neg;
int dis1 = 1 << d, dis2 = ~(dis1 >> 1), d2 = d * (d+1);
//最后一次特殊处理：中间结果（其实是最后的结果）不需要保存
if (d==DEPTH){
for (int k=0; k<dis1; k++) //枚举第一行所有可能
{
neg = nneg[k & MASK] + nneg[k >> HALF]; //用neg统计此符号三角形的负号总数。此时neg的值为当前行的负号数目
i=k^(k>>1); //算出第二行对应的整数
j = i & dis2 ; //去掉此整数最高位
neg += tag[delta1+j]; //neg加上后d-1行的负号总数
if ( neg<<2==d2 ) cnt[d]++;
}
return;
}
//枚举所有可能的三角形，并保存中间结果
for (int k=0; k<dis1; k++) //枚举第一行所有可能
{
neg = nneg[k & MASK] + nneg[k >> HALF]; //用neg统计此符号三角形的负号总数。此时neg的值为当前行的负号数目
i=k^(k>>1); //算出第二行对应的整数
j = i & dis2 ; //去掉此整数最高位
tag[delta2+k] = neg + tag[delta1+j]; //neg加上后d-1行的负号总数
if ( tag[delta2+k]<<2==d2 ) cnt[d]++;
}
delta1 += ~dis2;
delta2 += dis1;
ID(d+1);
}
int main()
{
//非常重要的加速！先求出[0..2^12-1]之间的数中所含1的数目，然后对于任何一个24位的数字m，
//把它的高12位中1的数目和低12位中1的数目加起来，就是m所含的1的数目！
//写成代码就是：nneg[m & MASK] + nneg[m >> HALF];
//通过增量方法求[0..2^12-1]之间的数中所含1的数目。即：先求1位的，再通过1位求2位的，再用2位求3位的……直至12位。
int half = 1 << HALF;
nneg[0] = 0;
nneg[1] = 1;
for (int cur=2, len = 2; cur<half; len<<=1){
for (int i=0; i<len; ++i)
nneg[cur++] = nneg[cur - len] + 1;
}
ID(1);
int n;
while (cin >>n && n)
cout << n << " " << cnt[n] << endl;
return 0;
}
例2
poj 3254 Corn Fields
题目描述
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
输入输出格式
输入格式：
第一行：两个整数M和N，用空格隔开。
第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。
输出格式：
一个整数，即牧场分配总方案数除以100,000,000的余数。
输入输出样例
输入样例#1：
2 3
1 1 1
0 1 0
输出样例#1：
9
（翻译来自luogu
这是一道很好的状压入门题。
开始前我们先预处理一下各种情况
我们先不管草地的情况和列的情况，单看行中的情况
每一行都是一样的！
都是隔一格放一个
那么我们就可以预处理一下每一行的情况。
那么如何转移呢
假如读入的时候我们用1表示不能放牧
那么假如现在的草地的情况为
草地：00010001
放牛：11001110
那么我们把这两个数&一下就成了
结果：00000000
也就是说，假如放牛与草地不冲突，那么它们&的结果就是0
这样就可以判断冲突了
假如要两列不冲突，其实是一样的，只要&一下就行了
这样就得出了方程
for i=1..n
for j=1..tot
if the i line is not conflict with the j's situation
for k=1..tot
if the i-1 line is not conflict with the k's situation
and the k's situation not conflict the j's situation
dp[i][j]+=dp[i-1][k]
i表示当前行，j表示当前行的情况，k表示上一行的情况
最后
注意细节
代码
#include <cstdio>
#define mod 100000000
using namespace std;
int dp[13][170];
int tot,n,m,x;
int sa[170];
int map[13];
int maxs;
void dfs(int now,int sat,int le)
{
if (now>m)
{
sa[++tot]=sat;
return;
}
for (int i=0;i<=1;i++)
if (!(le&i))
dfs(now+1,sat+i*(1<<now-1),i);
}
main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
scanf("%d",&x);
if (!x)
map[i]=map[i]|(1<<j-1);
}
dfs(1,0,0);
dp[0][1]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=tot;j++)
if (!(map[i]&sa[j]))
for (int k=1;k<=tot;k++)
if (!(sa[j]&sa[k])&&!(sa[k]&map[i-1]))
dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
for (int i=1;i<=tot;i++)
maxs=(maxs+dp[n][i])%mod;
printf("%d",maxs);
}
poj 1185 炮兵阵地
Description
司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用”H” 表示），也可能是平原（用”P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符(‘P’或者’H’)，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。
Output
仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
Sample Input
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
Sample Output
6
这道题和上一道题思路基本一样，可以检测一下
核心代码
for (i=1;i<=n;i++)
for (j=1;j<=tot;j++)
if (!(sa[j]&map[i]))
for (k=1;k<=tot;k++)
if (!(sa[j]&sa[k])&&!(sa[k]&map[i-1]))
for (l=1;l<=tot;l++)
if (!(sa[j]&sa[l])&&!(sa[l]&map[i-2]))
if (f[i][j][k]<f[i-1][k][l]+nu[j])
f[i][j][k]=f[i-1][k][l]+nu[j];
nu中存的是这一行中能放炮的数量
代码
#pragma GCC optimize (3)
#include <cstdio>
#define N 110
int maxs,f[N][N][N],map[N],sa[N],nu[N],n,m,tot;
void dfs(int now,int sat,int num,int le1,int le2)
{
if (now>m)
{
sa[++tot]=sat;
nu[tot]=num;
return;
}
for (int i=0;i<=1;++i)
if (i<=1-le1 && i<=1-le2)
dfs(now+1,sat+i*(1<<now-1),num+i,le2,i);
}
main()
{
int i,j,l,k,ans=0;
char c;
scanf("%d%d",&n,&m);
for (i=1;i<=n;++i)
{
c=getchar();
while(c!='H'&&c!='P')
c=getchar();
j=1;
while(c=='H'||c=='P')
{
if (c=='H')
map[i]+=j;
j<<=1;
c=getchar();
}
}
dfs(1,0,0,0,0);
for (i=1;i<=n;i++)
for (j=1;j<=tot;j++)
if (!(sa[j]&map[i]))
for (k=1;k<=tot;k++)
if (!(sa[j]&sa[k])&&!(sa[k]&map[i-1]))
for (l=1;l<=tot;l++)
if (!(sa[j]&sa[l])&&!(sa[l]&map[i-2]))
if (f[i][j][k]<f[i-1][k][l]+nu[j])
f[i][j][k]=f[i-1][k][l]+nu[j];
for(i=1;i<=tot;i++)
for(j=1;j<=tot;j++)
if(f[n][i][j]>maxs)
maxs=f[n][i][j];
printf("%d",maxs);
}
例4
poj 2411 Mondriaan’s Dream
Description
Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his ‘toilet series’ (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.
Expert as he was in this material, he saw at a glance that he’ll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won’t turn into a nightmare!
Input
The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.
Output
For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.
Sample Input
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
Sample Output
1
0
1
2
3
5
144
51205
题意就是用12和21的小块覆盖矩阵
这是一种不相同的状压
具体见这里吧
#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
long long dp[110][1<<12];
void init(int now,int sat)
{
if (now==m)
{
dp[0][sat]=1;
return;
}
if (now+1<=m)
init(now+1,sat<<1);
if (now+2<=m)
init(now+2,sat<<2|3);
}
void dfs(int now,int cur,int pre,int pos)
{
if (pos==m)
{
dp[now][cur]+=dp[now-1][pre];
return;
}
if (pos+1<=m)
{
dfs(now,cur<<1,pre<<1|1,pos+1);
dfs(now,cur<<1|1,pre<<1,pos+1);
}
if (pos+2<=m)
dfs(now,cur<<2|3,pre<<2|3,pos+2);
}
main()
{
while(1)
{
scanf("%d%d",&n,&m);
if (m==0&&n==0)
return 0;
if (n*m&1)
{
printf("0n");
continue;
}
memset(dp,0,sizeof dp);
init(0,0);
for (int i=1;i<n;i++)
dfs(i,0,0,0);
printf("%I64dn",dp[n-1][(1<<m)-1]);
}
}
To be continued…