【动态规划】状态压缩DP

前言

二进制的很多应用离不开集合这个概念，我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个int整形是4个字节，也就是32位bit，我们通过这32位bit上0和1的组合可以表示多大21亿个不同的数。如果我们把这32位bit看成是一个集合，那么每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的。那么我们可不可以用一个数来保存一维的DP状态呢？

这当然是可行的，动态规划的过程是随着阶段的增长，在每一个状态维护上不断扩展的。而对于某些题目，我们扩展时需要记录一个状态集合，保存状态信息，以便进行状态转移。而状态压缩则是把这一个大小不超过N、元素小于K的集合看做是一个N位的K进制数，以一个 $[0, K^N - 1]$ 之间的十进制整数的形式作为DP状态的一维。这样我们就可以只用一个十进制整数，就保存了一个状态信息——这就是状态压缩。

状态压缩的题目一般只有两种状态（当然也有三种状态的三进制题目）。这里只讨论最常见的二进制状态压缩，K进制状态压缩可以以此类推，不再赘述。

集合操作

在二进制状态DP中，我们用一个十进制整数代表一个集合，例如： $9 -> (1001)_{2}$ ，可以等效替换为一个bool数组 $B[4] = \{1, 0, 0, 1\}$ 。下面是集合的常用操作：

操作含义	代码
取出整数n在二进制表示下的第k位	(n >> k) & 1
取出整数n在二进制表示下的第0~k-1位（后k位）	n & ((1 << k) - 1)
把整数n在二进制下表示的第k位取反	n ^ (1 << k)
对整数n在二进制表示下的第k位赋值1	n\| (1 << k)
对整数n在二进制表示下的第k位赋值0	n & (~ (1 << k))
判断整数n在二进制表示下的第k位是否为真	n & (1 << (k - 1))

注意了！我们常说的第一位在二进制表示下其实是第零位，程序实现时一定要注意当前真正在操作的是哪一位，否则WA了很难找出错误。

上机实践

售货员的难题

经典例题，状态压缩DP入门题：P1171 售货员的难题。

构思（朴素算法）

看一下题目……最短路是吧？但是要求经过所有结点。

所以优先队列BFS最短路这种就不管用啦！那么既然要走过所有村庄，直接枚举全排列输出，暴力省事。时间复杂度为 $O(N * N!)$ ，属于是必死无疑。

下面给出一段基础搜索代码，包含基础剪枝，得分 $80Pt$ .

#include<cstdio>
using namespace std;
int lxy[21][21],hrb[21];
int n,i,j,k,minn=1e9;

int ss(int x,int y,int z)//x表示村子编号，y表示走了几个村子，z表示用的时间
{
    if(z > minn) return 0;//基本最小值剪枝
    if(y == n && z + lxy[x][1] < minn)
    {
	minn = z + lxy[x][1];
	return 0;
    }//比较求最小值，其中的加lxy[x][1]意思是走回第一个村
    for(int i = 2; i <= n; i++)//循环开始
    {
	if(hrb[i]==0&&i!=x)//深搜模板，没走就搜
	{
	    hrb[i] = 1;//打上标记
	    ss(i,y + 1, z + lxy[x][i]);
	    hrb[i] = 0;//回溯
        }
    }
    return 0;
}

int main()
{
    scanf("%d", &n);
    for(i = 1;i <= n; i++)
	for(k = 1;k <= n; k++)
	    scanf("%d", &lxy[i][k]);//输入
    ss(1, 1, 0);//开搜
    printf("%d",minn);
}