动态规划之状态压缩DP-NOIP提高组历年高频考点(2)
通过分析NOIP2011-2018年提高组的试题我们就会发现，考察最多的考点前三名就是模拟，动态规划和贪心算法。今天我们来介绍一下常见的状态压缩dp。
我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个int整形是4个字节，也就是32位bit，我们通过这32位bit上0和1的组合可以表示多大21亿个不同的数。如果我们把这32位bit看成是一个集合，那么每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的。我们用二进制的0和1表示一个二元集合的状态。可以简单认为某个物品存在或者不存在的状态。由于二进制的0和1可以转化成一个int整数，也就是说我们用整数代表了一个集合的状态。这样一来，我们可以用整数的加减计算来代表集合状态的变化。
状态压缩动态规划，就是我们俗称的状压DP，是利用计算机二进制的性质来描述状态的一种DP方式
很多棋盘问题都运用到了状压，同时，状压也很经常和ＢＦＳ及ＤＰ连用，例题里会给出介绍
有了状态，DP就比较容易了
通过题目要求减少状态量
这可以说是状压的一大精华了。一般状压的题目会有大量的状态，枚举所有状态则需要大量的时间，时间承受不了，若和dp结合起来，dp数组开个三四维，空间也吃不消。
所以我们可以通过预处理状态，去掉不合法的状态，减少时空的需要
具体实现和STL中的map很相似：我们用一个序号来映射状态，开一个数组INDEX[ ]（这里有坑，小写的index会和cstring库冲突 ）INDEX[i]表示第i个合法的状态是什么，然后枚举的时候直接枚举INDEX数组就好了
注意到m出奇的小，这就提示我们使用状态压缩模型来做。
先分析是否有后效性，发现任何一行在其下一行没有被放置的时候，都只受上一行的影响，于是满足了无后效性。
具体的做法是，把每一行的摆放情况看成一个二进制数，放了的地方是1，不放的地方是0，因此，每一种状态都可以用唯一一个数字来表示，于是就可以记录当前状态最多可以放多少个棋子了。
这里有一个优化，有些状态本身就是不合法的，如23（10111）在同行中就不满足，应该完全不考虑。所以，先进行预处理把所有可能的状态求出来是很必要的。
第一行的每一个状态的棋子数等于本身这个状态所拥有的棋子数。在状态转移中，第k行的第s个状态可以为k-1行所有可能的状态数的和加上本身状态所拥有的棋子数，至于两状态是否冲突，可以使用位运算判断。
最后，选择第n行记录最大数字的状态就是答案。
本算法的时间复杂度为O(n*(2^m)^2)，当m比较小时，此算法还是很快了。
由于状态压缩中使用的空间比较大，通常是指数级别的，所以推荐使用滚动数组来记录。
为了更好的理解状压dp，首先介绍位运算相关的知识。
1.’&’符号，x&y，会将两个十进制数在二进制下进行与运算，然后返回其十进制下的值。例如3(11)&2(10)=2(10)。
2.’|’符号，x|y，会将两个十进制数在二进制下进行或运算，然后返回其十进制下的值。例如3(11)|2(10)=3(11)。
3.’^’符号，x^y，会将两个十进制数在二进制下进行异或运算，然后返回其十进制下的值。例如3(11)^2(10)=1(01)。
4.’<<’符号，左移操作，x<<2，将x在二进制下的每一位向左移动两位，最右边用0填充，x<<2相当于让x乘以4。相应的，’>>’是右移操作，x>>1相当于给x/2，去掉x二进制下的最有一位。
这四种运算在状压dp中有着广泛的应用，常见的应用如下：
1.判断一个数字x二进制下第i位是不是等于1。
方法：if ( ( ( 1 << ( i - 1 ) ) & x ) > 0)
将1左移i-1位，相当于制造了一个只有第i位上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0，说明x第i位上是1，反之则是0。
2.将一个数字x二进制下第i位更改成1。
方法：x = x | ( 1<<(i-1) )
证明方法与1类似，此处不再重复证明。
3.把一个数字二进制下最靠右的第一个1去掉。
方法：x=x&(x-1)
感兴趣的读者可以自行证明。
一支炮兵部队能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入文件（cannon.in）
文件的第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。
输出文件（cannon.out）
文件仅在第一行包含一个整数K，表示最多能摆放的炮兵部队的数量。
数据规模就已经提示了本题的方法，动态规划的状态压缩。
不过对于这个题可没有那么简单，每一行的状态跟前两行有关，并且两行相互有干扰。说不简单也简单，于是考虑多记录些东西。用a[1..2^m,1..2^m]来记录两行共同的状态就可以了。至于初始情况和状态转移类似于上一题，所以不写了。本题同样需要先算出状态和使用滚动数组，最后再选取一个最大值即可。
程序：
{cannon_BY}
const bits:array[1..10]of integer=(1,2,4,8,16,32,64,128,256,512);
maxs=60;
maxn=100;
maxm=10;
var state:array[1..maxs]of integer;
stnum:array[1..maxs]of integer;
findm:array[1..maxm]of integer;
rlist:array[boolean,1..maxs,1..maxs]of integer;
rstr:string;
rn,rm,max,s,s1,s2,s3:integer;
now:boolean;
procedure init;
var co,tmp,s,s1:integer;
begin
co:=1;
for s:=1 to maxm do
begin
inc(co);
state[co]:=bits[s];
stnum[co]:=1;
tmp:=s-3;
if tmp>=1 then
for s1:=2 to findm[tmp] do
begin
inc(co);
state[co]:=bits[s]+state[s1];
stnum[co]:=1+stnum[s1];
end;
findm[s]:=co;
end;
end;
function rightstate(cstr:string;ns:integer):boolean;
var s:integer;
flag:boolean;
begin
flag:=true;
for s:=1 to rm do if (cstr[s]='H')and(ns and bits[s]=bits[s])then
begin
flag:=false;
break;
end;
rightstate:=flag;
end;
function matchstate(ns1,ns2:integer):boolean;
begin
if (ns1 and ns2)>0 then matchstate:=false else matchstate:=true;
end;
function getmax(inow:boolean):integer;
var s,s1,tmpmax:integer;
begin
tmpmax:=0;
for s:=1 to findm[rm] do
for s1:=1 to findm[rm] do if rlist[inow,s,s1]>tmpmax then tmpmax:=rlist[inow,s,s1];
getmax:=tmpmax;
end;
begin
init;
fillchar(rlist,sizeof(rlist),0);
readln(rn,rm);
now:=false;
for s:=1 to rn do
begin
readln(rstr);
now:=not now;
for s1:=1 to findm[rm] do
begin
if not rightstate(rstr,state[s1]) then continue;
for s2:=1 to findm[rm] do if matchstate(state[s1],state[s2])then
begin
max:=0;
for s3:=1 to findm[rm] do if matchstate(state[s1],state[s3])then
if rlist[not now,s2,s3]>max then max:=rlist[not now,s2,s3];
rlist[now,s1,s2]:=max+stnum[s1];
end;
end;
end;
writeln(getmax(now));
end.
位运算例题（结合BFS）：P2622 关灯问题II（来自：Tony_Double_Sky ）
题目描述
现有n盏灯，以及m个按钮。每个按钮可以同时控制这n盏灯——按下了第i个按钮，对于所有的灯都有一个效果。按下i按钮对于第j盏灯，是下面3中效果之一：如果a[i][j]为1，那么当这盏灯开了的时候，把它关上，否则不管；如果为-1的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是0，无论这灯是否开，都不管。
现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。
输入输出格式
输入格式：
前两行两个数，n m
接下来m行，每行n个数,a[i][j]表示第i个开关对第j个灯的效果。
输出格式：
一个整数，表示最少按按钮次数。如果没有任何办法使其全部关闭，输出-1
这题需要对状压及位运算有一定的了解：首先要判断某一位的灯是开的还是关的，才能进行修改。
具体解法是：对队首的某一状态，枚举每一个开关灯操作，记录到达这一新状态的步数（也就是老状态 + 1），若是最终答案，输出，若不是，压入队列。
也就是说：我们把初始状态，用每个操作都试一遍，就产生了许多新的状态，再用所有操作一一操作新状态，就又产生了新的新状态，我们逐一尝试，直到有目标状态为止，这可以通过BFS实现。
所以现在知道为什么状压比较暴力了吧。
# code
#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int RD(){
int out = 0,flag = 1;char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
return flag * out;
}
const int maxn = 2048;
int num,m,numd;
struct Node{
int dp,step;
};
int vis[maxn];
int map[maxn][maxn];
void BFS(int n){
queue<Node>Q;
Node fir;fir.step = 0,fir.dp = n;//初始状态入队
Q.push(fir);
while(!Q.empty()){//BFS
Node u = Q.front();
Q.pop();
int pre = u.dp;
for(int i = 1;i <= m;i++){//枚举每个操作
int now = pre;
for(int j = 1;j <= num;j++){
if(map[i][j] == 1){
if( (1 << (j - 1)) & now){
now = now ^ (1 << (j - 1));//对状态进行操作
}
}
else if(map[i][j] == -1){
now = ( (1 << (j - 1) ) | now);//对状态进行操作
}
}
fir.dp = now,fir.step = u.step + 1;//记录步数
if(vis[now] == true){
continue;
}
if(fir.dp == 0){//达到目标状态
vis[0] = true;//相当于一个标记flag
cout<<fir.step<<endl;//输出
return ;//退出函数
}
Q.push(fir);//新状态入队
vis[now] = true;//表示这个状态操作过了（以后在有这个状态就不用试了）
}
}
}
int main(){
num = RD();m = RD();
int n = (1 << (num)) - 1;
for(int i = 1;i <= m;i++){
for(int j = 1;j <= num;j++){
map[i][j] = RD();
}
}
BFS(n);
if(vis[0] == false)
cout<<-1<<endl;
return 0;
}