自动搬运

查看原文

来自洛谷，原作者为

	novax Tomori

搬运于2025-08-24 21:25:02，当前版本为作者最后更新于2020-07-19 21:59:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

updated 2020.10.10：更正了文中状态转移方程的错误

本题用到的知识点：

状压DP

状压 dp 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。 - OI wiki

状态压缩的思想是用二进制来表示状态。用一个整数的二进制形式的每一个二进制位 $0$ 或 $1$ 表示一个状态。

本题会涉及到部分位运算的知识

本题是一道比较基础的状压DP题目。

状压DP的时间复杂度为 $O(n^2 2^n)$，通常只能通过 $N \leq 21$ 的数据范围，本题数据范围为 $N \leq 15$ 因此可以使用状压DP。

思路

坐标可能为实数，因此要用double类型存储。

定义一个数组 $F_{i,j}$，表示老鼠走到第 $i$ 个奶酪，且走过的二进制状态为 $j$ 时，最短的距离。

举例来说，可以使用二进制 $10100110$ 来表示已经走过第 $2$、$3$、$6$、$8$ 个奶酪，此时 $j$ 的值为 $166$。需要注意的是，第 $i$ 个状态是从低位向高位的第i位。

在更新 $F$ 数组状态时会用到两点间的距离，使用两点间距离公式计算：

$a = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

首先要将 $F$ 数组进行初始化为极大值，可以使用memset(F,127,sizeof(F));来为浮点数赋极大值

因为到达第 $i$ 块奶酪，且只经过过第 $i$ 块奶酪的距离即为第i块奶酪与坐标原点的距离。因此要初始化F[i][(1<<(i-1))]=a[0][i];。

接下来是三层循环，分别枚举所有可能的二进制状态、当前点所在的位置和能在当前状态下到达当前点的位置。

在第二层循环中要判断一下 $i$ 在当前二进制状态下是否已走过，如果根本没走过则不需要进行接下来的计算，直接continue就可以。

在第三层运算中同样要判断当前点是否已走过，且当前点不与 $i$ 点相同。

接下来就可以转移状态了：

设此时二进制状态为 $k$，终点为 $i$，起点为 $j$，可得状态转移方程：$F_{i,k}=\min(F_{i,k},F_{j,k-{2^{i-1}}} +A_{i,j})$。$F_{j,k-{2^{i-1}}}$ 为在 $j$ 点且没有走过 $i$ 点的最短距离， $A_{i,j}$ 是从 $i$ 到 $j$ 的距离。

最后，找出 $F_{i,2^N-1}$ 中的最小值就是最终的答案了。

代码如下

#include <cstdio>
#include <cstring> 
#include <cmath> 
#define min(a,b) (((a)<(b))?(a):(b)) 
//洛谷 P1433 吃奶酪 状压DP
double a[20][20];//预处理，从第i块到第j块的距离，使用两点之间距离公式 
double x[20],y[20];//每块奶酪的横、纵坐标
double F[18][34000];//状压DP数组 在第i个点上，走过的二进制状态的十进制表达为j时，最短的距离 
int N; 
double distance(int v,int w)//计算第v个和第w个奶酪之间的距离 
{
	return sqrt((x[v]-x[w])*(x[v]-x[w])+(y[v]-y[w])*(y[v]-y[w]));//两点间距离公式 
}
int main()
{
	int i,j,k;
	double ans;
	memset(F,127,sizeof(F));//这样可以给浮点数赋值无穷大 
	ans=F[0][0];
	scanf("%d",&N);
	for(i=1;i<=N;i++)
	{
		scanf("%lf%lf",&x[i],&y[i]);//数据读入 
	}
	x[0]=0;y[0]=0;
	for(i=0;i<=N;i++)
	{
		for(j=i+1;j<=N;j++)
		{
			a[i][j]=distance(i,j);//初始化距离数组 
			a[j][i]=a[i][j];
		}
	} 
	for(i=1;i<=N;i++)//初始化 
	{
		F[i][(1<<(i-1))]=a[0][i];//在i点上且只有经过i点时距离是原点到i点的距离 
	}
	for(k=1;k<(1<<N);k++)//枚举所有二进制的状态 
	{
		for(i=1;i<=N;i++)
		{
			if((k&(1<<(i-1)))==0)
				continue;//i的位置没被走过，所以不需要再继续计算了 
			for(j=1;j<=N;j++)
			{
				if(i==j)
					continue;//同一个点不需要再计算 
				if((k&(1<<(j-1)))==0)
					continue;//j的位置没走过  
				F[i][k]=min(F[i][k],F[j][k-(1<<(i-1))]+a[i][j]);
			} 
		} 
	} 
	for(i=1;i<=N;i++)
	{
		ans=min(ans,F[i][(1<<N)-1]);
	}
	printf("%.2f\n",ans);
}