状态压缩DP

状态压缩DP前置知识

问题简介
基于状态压缩的动态规划，又叫集合动态规划。顾名思义，这是一类以集合信息为状态的特殊的动态规划问题。主要有传统集合动态规划和基于连通性状态压缩的动态规划两种。
一般的动态规划往往着眼于整体，从中提取出两三个关键信息，并依此划分阶段使得问题具备无后效性及最优子结构性质，然后根据已知信息依次对各个阶段进行决策。然而有时候一般的状态描述难以满足无后效性原则，或者保存的信息不足以进行决策，许多元素的状态都直接影响到决策，都需要被考虑到。为每一个元素的状态都开一维数组来存储显然是行不通的，于是就需要有一种便于识别和操作的方式记录下各个元素的状态，即对多个元素的状态进行压缩存储，于是基于状态压缩的动态规划应运而生。

我们通常把这样一类以状态且状态总数为指数级别的动态规划称为基于状态压缩的动态规划或集合动态规划。基于状态压缩的动态规划问题通常具有以下两个特点。
①数据规模的某一维或几维非常小。
②它需要具备动态规划问题的两个基本性质：最优性原理和无后效性

二、基于状态压缩的动态规划 预备知识
位操作是一种速度非常快的基本运算：有左移、右移、与、或、非等运算。
左移：左移一位，相当于某数乘以2，比如110左移1位变为110096变为12，表示为(110<<1)
1100。因此左移x位，相当于该数乘以2
右移：右移一位，相当于某数除以2，比如110右移1位变为11÷6变为3，表示为(110>>1)
=11。因此右移x位，相当于该数除以2x。
与运算：按位进行“与”运算，两数同一位都为1时结果为1，否则为0。例如:101&110=100。
或运算：按位进行“或”运算，两数同一位都为0时结果为0，否则为1。例如:101|110=11l。
非运算：按位取反。例如~101=010。

若当前状态为s，对s有下列操作。
①判断第i位是否为0：(S&&(1<<i)==0，意思是将1左移i位与S进行与运算后，看结果
是否为0
②将第i位设置为1：S|(1<<i)，意思是将1左移i位与S进行或运算。
③将第i位设置为0：S&~(1<<i)，意思是S与第i位为0，其余位为1的数进行与运算。

例如:S=1010101,i=5。注意二进制位从0开始计数，所以i=5实际上是第6位
S&(1<<i):1010101&0100000=000000
S|(1<<i):1010101|0100000=1110101。
S&~(1<<i):1010101&1011111=1010101。

二进制表达想必学过一些二进制的人都知道吧，我们需要做的仅仅是摒弃它的十进制的模样（别影响了自己的理性思维）。假设现在有一个集合S=∅S=∅，表示为二进制就是00000000（假装只有8位），然后我们将第0位置1，也就是S=S∪{0}=S∨20=S|1<<0。同理，如果将里面的第六位置1，就是S|=1<<6.
如果是判断u是否存在于集合S中的话，那么只需要判断S∨2u（即C++中的S&(1<<u)）是否为真就可以了。因为后者仅第u位是1，其它部分都是0，而与的性质是二者都真时才为真，故达到了判断的目的。

例题：牧场安排
【题目解析】
状态压缩类动态规划。可将每一排的N个看成一个N位2进制数，先预处理出每一行可以运用的状态，这样可以去掉很多无效的状态(如110)，然后DP处理，枚举当前有效状态和上一行有效状态的关系。
在只考虑第一行的时候，有5种可行的放牧方案：开辟0块草地有1种方案，开辟1块草地有3种方案，开辟两块草地有1种方案，如下图

首先思考：纳入第二行后，会对当前问题造成什么样的影响？

答案还是那句话：“相邻格子不可同时放牧”！

也就是说，不止左右相邻不可以，上下之间也不能存在相邻的情况。

首先观察第二行，只有中间的格子可以放牧，那么我们的状态表格就可以相对简单些了～如下：

只有两种可行状态，那么我们不妨一个一个来考察：
1、当第二行的状态为编号1时，第二行的三个格子都没有放牧，那么就不会与第一行的任何情况有冲突，第一行的5种方案都可行，即：第二行选用编号1的状态时，结合第一行，可得到5种可行的放牧方案；

2、当第二行的状态为编号2时，第二行中间的格子已经放牧了，那么第一行中间的格子就不可以放牧。发现其中第3种状态与当前第二行冲突，那么第一行只有4种方案是可行的，即：第二行选用编号2的状态时，结合第一行，可得到4种可行的放牧方案；
那么，在样例数据给出的情况下，我们的最终答案即为5+4=9；

通过对样例数据的分析即可以发现不同状态之间的关系：
以f[i][state(j)]来表示对于前i行，第i行采用第j种状态时可以得到的可行方案总数！
例如：回头看样例数据，f[2][1]即代表第二行使用第1中状态（0 0 0）时可得的方案数，即为5；
那么，可得出状态转移方程为：
f[i][state(j)]=f[i-1][state(k1)]+f[i-1][state(k2)]+…+f[i-1][state(kn)](kn即为上一行可行状态的编号，上一行共有n种可行状态）
最终ans=f[m][state(k1)]+f[m][state(k2)]+…+f[m][state(kn)]; (kn即为最后一行（第m行）

【总结题解核心】

把每一行的状态存入Line[]。
f[i][j]表示1−i行，并且第i行状态为j时的合法方案数。
考虑状态的转移，既然要求转移合法，我们就来考虑一下合法的条件：
1.1.当前枚举的状态j与对应的Line[i]不冲突，
2.2.当前枚举的状态j与上一层的某状态k不冲突，
3.3.当前枚举的状态自身没有连续的1，
如果枚举出来的当前层状态j与上一层状态k满足上面三个条件，就可以进行累加转移：
f[i][j]+=f[i−1][k]
然后累加答案即可。

#include <bits/stdc++.h>
using namespace std;
const int Mod=1e8;
const int Inf=1e9;
int DP[13][1<<13];
int N,M,T,Ans,Line[13],Map[13][13];
int main(){
    int I,J,K;
    scanf("%d%d",&N,&M);T=(1<<M)-1;
    for(I=1;I<=N;I++){
        for(J=1;J<=M;J++){
            scanf("%d",&Map[I][J]);
            if(Map[I][J]==1){
                Line[I]=Line[I]|(1<<(J-1));
            }
        }
    }
    for(I=0;I<=T;I++){
        if((I|Line[1])==Line[1]&&((I>>1)&I)==0&&(I&(I<<1))==0){
            DP[1][I]=1;
        }
    }
    for(I=2;I<=N;I++){
        for(J=0;J<=T;J++){
            for(K=0;K<=T;K++){
                if((J|Line[I])==Line[I]&&(J&K)==0&&((J>>1)&J)==0&&(J&(J<<1))==0){
                    DP[I][J]=(DP[I][J]+DP[I-1][K])%Mod;
                }
            }
        }
    }
    for(I=0;I<=T;I++){
        Ans=(Ans+DP[N][I])%Mod;
    }
    printf("%d",Ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

例题：售货员的难题
【解析】
f[V][0]=0
f[S][v]=min{f[S∪{u}][u]+d(v,u)|u∉S}

其中f[S][v]表示的是从v出发访问所有不属于集合S的顶点，最终回到0的路径的权重总和的最小值。而集合V表示为所有城市的集合，不难理解从0到0就是路程为0对吧，并且再将其它所有情况均赋值为无穷大

注意到我们的int可以表示到2³¹−1，然而这里的N才这么大一点，那么我们就可以在二进制位中逐位保存某个点“存在”和“不存在”的情况。再者，这只需涉及到二进制的位运算，所以整体来说还是很快的。
下面这段代码仅能得到80分，但是开O2可以险过。

#include <cstdio>
#include <algorithm>
#define INF 20000
using namespace std;
int f[(1<<20)][20], d[20][20];
int main()
{
    int i, j, k, n, smax;
    scanf("%d", &n);
    smax = (1 << n) - 1;
    for(i = 0; i < n; i += 1)
        for(j = 0; j < n; j += 1)
            scanf("%d", &d[i][j]);
    for(i = 0; i <= smax; i += 1)
        for(j = 0; j < n; j += 1)
            f[i][j] = INF;
    f[smax][0] = 0;
    for(i = smax-1; i >= 0; i -= 1)
        for(j = 0; j < n; j += 1)
            for(k = 0; k < n; k += 1)
                if(!(i >> k & 1) && j != k)
                    f[i][j] = min(f[i][j], f[1<<k|i][k] + d[j][k]);
    printf("%d", f[0][0]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

回过头来我们再看一下这个递推式，实际上还有优化的地步！
f[S][v]=min{f[S∪{u}][u]+d(v,u)|u∉S}
注意到min中的f[S∪{u}][u]保证了u必然在集合S∪{u}里面，有人可能会说这是废话，但是这说明了在前面的状态中，v必然在集合S里面啊！因此对于v不在集合S中的情况就不必考虑了。但是，注意当S为空（程序中变为0）的时候它就不会继续走答案了，也就是说我们要特殊处理一下这种情况。
于是我们得到了90分代码。

#include <cstdio>
#define INF 20000
int f[(1<<20)][20], d[20][20];
inline int cmin(int a, int b)
{
    return a < b ? a : b;
}
int main()
{
    int i, j, k, n, smax;
    scanf("%d", &n);
    smax = (1 << n) - 1;
    for(i = 0; i < n; i += 1)
        for(j = 0; j < n; j += 1)
            scanf("%d", &d[i][j]);
    for(i = 0; i <= smax; i += 1)
        for(j = 0; j < n; j += 1)
            f[i][j] = INF;
    f[smax][0] = 0;
    for(i = smax-1; i; i -= 1)
        for(j = 0; j < n; j += 1)
            if(i >> j & 1)/*添加1*/
                for(k = 0; k < n; k += 1)
                    if(!(i >> k & 1))
                        f[i][j] = cmin(f[i][j], f[1<<k|i][k] + d[j][k]);
    int ans = INF;
    for(i = 1; i < n; i += 1)/*添加2*/
        ans = cmin(ans, f[1 << i][i] + d[0][i]);
    printf("%d", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

那，不开O2怎么拿100分呢？答案是舍去多考虑的必然不存在的情况，也就是必然为INF的情况。
让我们再从头开始看，看那个递推式（稍改）。
f[V][0]=0
f[S][v]=min{f[S∪{u}][u]+d(v,u)|u∉S,v∈S}
最开始S二进制位（位数小于N）全部是1的时候，仅0号点为0，其它都是INF。而有些INF是可以推到底层的！那什么样的情况满足其f恒为INF呢？首先注意到f[V][x],x≠0的情况恒为INF，那这个状态又会推到哪里呢？根据递推式：
f[S][v]=min{f[S∪{u}][u]+d(v,u)|u∉S,v∈S}
我们有：
f[S][v]=min{f[V][u]+d(v,u)|u≠{0},u∉S,v∈S}
容易得到f[S][v]必然为INF（因为u只有一种可能）。
同理，对于递推式：
f[S][v]=min{f[S∪{u}][u]+d(v,u)|{0}∈S,u∉S,v∈S}
f[S][v]必然由一个比当前集合S（包含元素0）多一个元素的集合S′得来，而S′又以类似方式得来，最终它们共同的来源均为：
f[V][u]+d(v,u)|u≠{0},u∉S,v∈S
故对于任何满足{0}∈S的f[S][v]，它们的值恒为INF。用二进制表示法来说，只要S&1为真，那么就无需考虑。
那么程序就可以“进化”了，从而拿到100分！

#include <cstdio>
#define INF 20000
int f[(1<<20)][20], d[20][20];
inline int cmin(int a, int b)
{
    return a < b ? a : b;
}
int main()
{
    int i, j, k, n, smax;
    scanf("%d", &n);
    smax = (1 << n) - 1;
    for(i = 0; i < n; i += 1)
        for(j = 0; j < n; j += 1)
            scanf("%d", &d[i][j]);
    for(i = 0; i <= smax; i += 1)
        for(j = 0; j < n; j += 1)
            f[i][j] = INF;
    f[smax][0] = 0;
    for(i = smax-1; i; i -= 2)
        for(j = 0; j < n; j += 1)
            if(i >> j & 1)
                for(k = 0; k < n; k += 1)
                    if(!(i >> k & 1))
                        f[i][j] = cmin(f[i][j], f[1<<k|i][k] + d[j][k]);
    int ans = INF;
    for(i = 1; i < n; i += 1)
        ans = cmin(ans, f[1 << i][i] + d[0][i]);
    printf("%d", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

练习题目

1、互不侵犯
2、关灯问题
3、宝藏