来自一个菜鸡的总结。
先说说什么是状态压缩dp吧。
状态压缩dp的定义
1.Definition：状态压缩dp的是一种对dp表示形式优化的dp。
说得通俗点，就是把dp数组的维度降低。
而我们举一个具体的例子看看：Vjudge.4124。
这道题目看了之后，可以发现是一个明显的汉密尔顿环问题。
科普一下，汉密尔顿环问题就是一种求不重复地经过所有点的问题。
而这仍然是一个NP难题，我们用一个 \(O(2^n\times n^2)\) 的算法解决它。
其实有一个非常朴素的思路：
开一个16维的dp数组，一维记录每一个岛屿有没有走过！
时间复杂度上没有问题。
但是，你觉得这样打起来真的舒服吗？这就变成琪露诺的冰雪小屋了（（（
所以，状态压缩就出场啦！
我们用一个二进制数来记录这个有没有走过这些岛屿。
而思路已经清楚了，我们来想想具体实现。
不过先总结一下状压dp的一些东西。
2.Features：[经验之谈了属于是]
(1)有两种状态的表述（有的题也许有三种）；
(2)数据范围一般较小，大概十几；
(3)求解目标为方案数或者极值。//dp的feature啦。
3.常用的位操作：
这个非常非常重要！
（下次打上来，我有点懒）
板子题的实现
于是这个海贼王的什么什么就可以实现粗来了。
这里以卡到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<bits/stdc++.h>
#define ll long long
#define ri register int
using namespace std;
const int MAXN=17;
int n,w[MAXN][MAXN],dp[(1<<MAXN)-1][MAXN];
int main() {
ios::sync_with_stdio(false);
memset(dp,0x3f,sizeof(dp));
cin>>n;
for(ri i=0;i<n;i++){
for(ri j=0;j<n;j++){
cin>>w[i][j];
}
}
dp[1][0]=0;
for(ri i=1;i<=(1<<n)-1;i+=2){//优化
for(ri j=1;j<n;j++){
if(((i>>j)&1)==0)continue;//排除不合法状态
for(ri k=0;k<n;k++){
if(((i>>k)&1)==0)continue;
dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+w[k][j]);
}
}
}
cout<<dp[(1<<n)-1][n-1];
return 0;
}
差不多得了.jpg
经典的题
这道题没有什么难点吧，上一道题稍微改一下就OK了。
往返也就加一个 \(w[i][0]\) 就行了。