状态压缩dp学习笔记

来自一个菜鸡的总结。

先说说什么是状态压缩dp吧。

状态压缩dp的定义

1.Definition：状态压缩dp的是一种对dp表示形式优化的dp。

说得通俗点，就是把dp数组的维度降低。

而我们举一个具体的例子看看：Vjudge.4124。

这道题目看了之后，可以发现是一个明显的汉密尔顿环问题。

科普一下，汉密尔顿环问题就是一种求不重复地经过所有点的问题。

而这仍然是一个NP难题，我们用一个 \(O(2^n\times n^2)\) 的算法解决它。

其实有一个非常朴素的思路：

开一个16维的dp数组，一维记录每一个岛屿有没有走过！

时间复杂度上没有问题。

但是，你觉得这样打起来真的舒服吗？这就变成琪露诺的冰雪小屋了（（（

所以，状态压缩就出场啦！

我们用一个二进制数来记录这个有没有走过这些岛屿。

而思路已经清楚了，我们来想想具体实现。

不过先总结一下状压dp的一些东西。

2.特征：

(1)有两种状态的表述（有的题也许有三种）；

(2)数据范围一般较小，大概十几；

(3)求解目标为方案数或者极值。//dp的特征

3.常用的位操作：

重点！

先看一下一些基本的位运算符号：

(1)\(&\)，表示两位如果都是 \(1\) 就返回 \(1\)。（\(x&y\) 为其返回结果）

(2)\(^\)，表示两位如果不同就返回 \(1\)。

(3)\(|\)，表示两位有一个是 \(1\) 就返回 \(1\)。

(4)\(~\)，直接取反。（即把 \(1\) 变成 \(0\)，\(0\) 变成\(1\)）

(5)\(>>\)，右移，即在二进制下整体往右移动。（\(x>>k=x\div2^k\)）

(6)\(<<\)，左移，即在二进制下整体往左移动。（\(x<）

然后再看一些位运算符号的运用：

(1)任何二进制数位 \(&1\) 或 \(^0\) 得本身。

(2)任何二进制数位 \(^1\) 取反。

(3)任何二进制数位 \(&0\) 赋值为 \(0\)。

(4)任何二进制数位 \(|1\) 赋值为 \(1\)。

(5)\((1< 表示二进制下 \(k\) 个 \(1\) 组成的数。//很常用

状压dp里面常用的小操作：

(1)\((n>>k)&1\) ->取出二进制下 \(n\) 的从右往左数第 \(k\) 位。

(2)\(n&((1< ->取出二进制下 \(n\) 的右 \(k\) 位。

(3)\(n^(1< ->将二进制下 \(n\) 的第 \(k\) 位取反。

(4)\(n|(1< ->将二进制下 \(n\) 的第 \(k\) 位赋值为\(1\)。

(5)\(n&(~(1< ->将二进制下 \(n\) 的第 \(k\) 为赋值为 \(0\)。

都很重要。

板子题的实现

于是这个海贼王的什么什么就可以实现粗来了。

这里以卡到85ms的代码为例吧。

1.状态：定义 \(dp[i][j]\) 表示走到 \(j\) 点时，并且点的访问情况为二进制的 \(i\) 的最少花费。

2.状态转移：[伪代码]

for(循环断点k){
    if(如果j在i中的状态为0，即没去过)continue;
    dp[i][j]=min(dp[i][j],dp[j没有走过时的二进制状态][k]+w[k][j]);
}

3.初始值

dp[1][0]=0;

此时我们假定从第0位用起。-->节省空间

上卡过常的代码：

#include
#define ll long long
#define ri register int
using namespace std;
const int MAXN=17;
int n,w[MAXN][MAXN],dp[(1<>n;
	for(ri i=0;i>w[i][j];
		}
	}
	
	dp[1][0]=0;
	for(ri i=1;i<=(1<>j)&1)==0)continue;//排除不合法状态
			for(ri k=0;k>k)&1)==0)continue;
				dp[i][j]=min(dp[i][j],dp[i^(1<