Oak_limy 的 博客

状压dp

指二进制状态压缩dp

例题

最短 Hamilton 问题
题面：给定一张 n(n $\leq$ 20)个点的带权无向图，点从0 $\sim$ n-1标号，求起点 0 到终点n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
做法
很容易想出来朴素做法，枚举 n 个点的全排列，计算路径长度去最小值，复杂度位 $O(n \times n!)$
接下来就是状压dp做法，它的复杂度位 $O(n^2\times 2^n)$
我们可以用一串 n 位的二进制数来表示哪些点被经过了，如果第i位为1代表被经过，反之则没有。
我们还需知道当前所处的位置，我们设 $F[i][j]$ 表示当前被经过的点的二进制数状态和当前处于第j个点。
我们在起点时要设 $F[1][0]=0$因为经过0点所处位置为0，最短路长度为0。其余的，我们设F数组为无穷大
转移方程为 F[i][j]=min{F[i xor (1<<j),k]+dist[k,j] 其余的微观细节看代码吧

int n;
int dp[1<<20][20],dis[20][20];
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>dis[i][j];
		}
	}
	memset(dp,0x3f,sizeof(dp));      //设无穷大
	dp[1][0]=0;  //边界条件
	for(int i=0;i<(1<<n);i++){        //每种状态枚举
		for(int j=0;j<n;j++){
			if((i>>j)&1){          //如果这位来过 则可以尝试连接k和j  这一点类似floyd
				for(int k=0;k<n;k++){
					if((i>>k)&1){    //k来转移  
						dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+dis[k][j]);   //松弛操作
					}
				}
			}
		}
	}
	cout<<dp[(1<<n)-1][n-1]<<endl;             //最终的状态11111···     n个点
	return 0;
}