[算法]状压dp

关键词：状压使用场景、思路、应用

状压dp是字面意思将状态压缩，一般是压缩至二进制，所以n需要很小，普遍都是 \(n \le 20\).

例题1：简化题目从(0,0)出发，走过所有节点的最短路长度多少

设f[mark][i]定义为状态为mark且最后到达第i个奶酪位置,mark状态定义为当第j位为1的时候表示经过第j个奶酪的位置

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
const double inf = 1e20;
int n;
double f[1<<maxn][maxn];
struct node{double x=0,y=0;
}a[maxn];
double add(int i,int j){return sqrt(pow(a[i].x-a[j].x,2)+pow(a[i].y-a[j].y,2));
}
int main(){cin>>n;for(int s=0;s<(1<<n);s++){for(int i=1;i<=n;i++){f[s][i]=inf;}}for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;f[1<<(i-1)][i]=add(0,i);}for(int s=0;s<(1<<n);s++){for(int i=1;i<=n;i++){if(!(s&(1<<(i-1))))continue;for(int j=1;j<=n;j++){if(s&(1<<(j-1)))continue;f[s|(1<<(j-1))][j]=min(f[s|(1<<(j-1))][j],f[s][i]+add(i,j));}}}double ans=inf;for(int i=1;i<=n;i++){//cout<<f[(1<<n)-1][i]<<" ";ans=min(ans,f[(1<<n)-1][i]);}printf("%.02lf\n",ans);return 0;
}