动态规划之状态压缩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数组就好了

    

有一些动态规划的状态并不是放与不放，取与不取，选与不选那么简单。状态可能因为情况而变得很多，比如在一个n*m（n<=500,m<=10）的棋盘里面放棋子，有些格子被挖掉不能放棋子，并且任何两个棋子不得有上下左右的相邻，问最多放多少个棋，该怎么做呢？

注意到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)

感兴趣的读者可以自行证明。

有一些状态压缩模型并不是描述前一行的状态就可以了这么简单，如NOI2001的炮兵阵地一题：

    司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示）。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）。

    一支炮兵部队能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。炮兵的攻击范围不受地形的影响。

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

输入文件（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;

    }