更好的阅读体验

状态压缩动态规划学习笔记

算法介绍

状态压缩动态规划是近些年来NOIP提高组常考的算法,也是日后ACM必备的算法之一,因此我们有必须要学习此类高级算法.而且此类算法往往是NP算法的最强优化之一.

算法思想

状态压缩动态规划,顾名思义也就是,将动态规划中的状态数组进行了压缩.
那么想到压缩,我们不免就要想到一种常用的时间空间优化技巧,或者说一种特殊的算法,也就是位运算.

卡常算法就是它,高端暴力就是它,奇迹算法还是它.

位运算,也就是二进制的运算,而且我们的二进制,是一种计算机中最为核心的编码,这也就是为什么,电脑对于这种编码运算速度最快.

状态压缩动态规划,就是利用了位运算,的这三大优化性质,来起到简化代码,优化代码,解决难题的目的.

位运算基础

判断算法

首先拿到一道题目,我们第一步就是要看数据范围,题目描述. 而且当你发现数据范围和题目描述具有以下三大特点的时候,那么我们就可以初步判断这道题目需要使用状态压缩动态规划.

1. 数据中的N,M范围很小,基本上不超过30,20.(N,M广义理解)
2. 题目似乎要我们求方案数,或者说极值问题.
3. 题目似乎是个棋盘覆盖这种类型的问题.

算法处理

一般来说,状态压缩动态规划算法,最为困难,也是最为关键的一步,就在于
$$ {\color{red}{状态如何以二进制表示}} $$
那么接下来我就来详细解说,状态压缩的状态到底如何设置.

一般来说状态设置,往往是一个整数,表示一个二进制决策集合.

比如说13,它就可以表示为1011,那么我们一般来说可以表示第一个点,第二点,第四个点已经选择这个意思.

因为我们可以确定算法为状态压缩,那么我们现在的主力攻击,就是状态设置,既然现在我们已经有了这个目标,显然我们就是尽量地将题目的条件进行转化,在这里我们具体以棋盘类型来分析.

对于条件而言的话,我们需要捕捉到关键点.

1. 如果说题目中出现了这一个点不可以选择,那么你的神经中枢第一时间就要条件反射地,对自己的内心说一句,这里是1.

这里是1到底是什么意思?其实这个意思,就是告诉我们这个点不可以选择,我们可以通过开一个特殊数组来保存,那么到了以后,对于我们枚举的一个决策集合,那么我们可以通过&运算,来判断这个点是否可以选择.

比如说我们现在要求第五个点不可以选择,那么我们可以构造一个判断数组.10000表示第五个点不可以选择.

那么假如说我们当前枚举的状态决策集合是11000,这个意思是,我们当前选择第四个点和第五个点.

那么我们可以通过&运算,来进行判断.

11000的十进制表示为24,而我们10000表示为16.那么我们进行&运算.

24&16 ==> 11000 & 10000 ==> 16 ==> 10000

总结:所以说我们可以通过&运算,进行判断是否选择.同理,如果题目说必须选择,显然&运算也可以发挥作用.

其他运算操作以后再慢慢补充吧,我们先来几道题目感受感受.

题目选讲

第一题

题目描述

求把$N \times M$的棋盘分割成若干个$1 \times 2$的的长方形，有多少种方案。

例如当$N=2，M=4$时，共有5种方案。当$N=2，M=3$时，共有3种方案。

如下图所示：

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含两个整数N和M。

当输入用例

$N=0 M=0$时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个结果，每个结果占一行。

数据范围

$$ 1 \le N,M \le 11 $$

输入样例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
0
1
2
3
5
144
51205

题意解析

首先这道题目题意很好理解,我就不说一句话题意了,但是我们要明确这道题目给我们的信息.

1. 条件:1*2的长方形,有竖着的,也有横着的.
2. 性质:棋盘性质,数据范围很小
3. 最后答案 所有的合法方案数

通过上面给我们的信息,我们不难判断这道题目是一道状态压缩动态规划算法,那么接下来我们按照上面所说的,我们现在需要处理如何二进制化状态.

算法解析

我们发现,对于任何一个方案而言,假如说我们现在目光定格在,某一行的话,换句话说把棋盘分成两部分,那么我们似乎会发现什么有趣的东西.

我们发现如果说我们确定了第一排的红色,那么显然绿色也随着确定了.

而且如果我们确定了第一排的红色,那么同样的我们的第二排一部分红色也就绝对确定了.切记不是所有的红色.

因此我们显然可以认为红色为1,绿色为0,因为这道题目除了红色摆放,就是绿色摆放了,所以说这就是这道题目二进制的状态转化.

状态处理

综上所述,我们就可以把行号看作阶段.
接着我们可以设$f[i][j]$表示为第i行决策集合为j.(j为二进制集合,不过用十进制存储)

那么接下来我们就要看决策的条件了.

对于$f[i-1][k]$转移到$f[i][j]$显然是有两个条件的.
1. j&k==0 也就是说每个数字1的下面必须是数字0,否则无法放入12的竖着长方形
2. j|k的二进制表示中,每一段连续的0个数必须为偶数,否则无法放入12的横着长方形.

代码解法

#include <bits/stdc++.h>
using namespace std;
const int N=11;
long long f[12][1<<N];
int n,m;
bool st[1<<N];
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m && n)
    {
        for(int i=0;i<1<<m;i++)//预处理,处理所有[0,2^m -1]内所有满足二进制表示下每一段连续01都有偶数个的整数.
        {
            bool cnt=0,odd=0;
            for(int j=0;j<m;j++)
                if (i>>j & 1)//判断第j是否选择了
                    odd|=cnt,cnt=0;
                else
                    cnt^=1;
            st[i]=odd|cnt?0:1;
        }
        f[0][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=0;j<(1<<m);j++)//枚举状态.
            {
                f[i][j]=0;//初始化
                for(int k=0;k<(1<<m);k++)
                    if ((j&k)==0 && st[j|k])//满足上面说的条件
                        f[i][j]+=f[i-1][k];//转移过来了
            }
        cout<<f[n][0]<<endl;//最后的结果
    }
    return 0;
}