自动搬运

查看原文

来自洛谷，原作者为

	chen_kun 生命绚烂，别被黑暗压垮。

搬运于2025-08-24 23:13:48，当前版本为作者最后更新于2025-06-10 17:29:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解：P12220 [蓝桥杯 2023 国 Java B] 星球

思路简述

可以看到 $n$ 的范围很小，再好好看看题面，可以发现这是一道典型的旅行商问题变种，只是从二维平面变成了三维立体，考虑使用状压 DP 求解。

所谓状压 DP，其精髓在于状态压缩，通过将状态转化为二进制的方式进行动态规划，利用二进制中只有 $1$ 和 $0$ 的特性表示某点是否达到某个目的。具体处理不再过多赘述。

定义 $dp_{i,j}$ 为当状态为 $i$，最后到达的点为 $j$ 时的所需的最小能量。通过空间中两点距离公式 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$ 及题目中给到的公式即可得到状态转移方程:

dp[i][j]=min(dp[i][j],dp[i^(1<<j-1)][k]+dis(a[j].x,a[j].y,a[j].z,a[k].x,a[k].y,a[k].z)*a[j].w);。

其中 $j$ 代表 $i$ 状态的结束点，$k$ 表示到达 $j$ 之前状态的结束点。

代码呈现

C++

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20;
int n,m;
double dp[1<<N][N],mmin=DBL_MAX;
struct node{int x,y,z,w;}a[N];
double dis(int x,int y,int z,int xx,int yy,int zz){return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y)+(zz-z)*(zz-z));}//空间中两点计算公式 
signed main(){
	cin>>n;
    memset(dp,127,sizeof(dp));
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].z>>a[i].w,dp[1<<i-1][i]=0;
	dp[0][0];
	int num=1<<n;
	for(int i=0;i<num;i++)
		for(int j=1;j<=n;j++)
			if((i>>j-1)&1)//确保j在状态i中 
				for(int k=1;k<=n;k++)
					if((i>>k-1)&1)//确保k在状态i中 
						dp[i][j]=min(dp[i][j],dp[i^(1<<j-1)][k]+dis(a[j].x,a[j].y,a[j].z,a[k].x,a[k].y,a[k].z)*a[j].w);//利用题目中能量的计算公式进行转移 
    for(int i=1;i<=n;i++) mmin=min(mmin,dp[num-1][i]);//枚举不同的结束点取最小值 
	printf("%.2lf",mmin);
	return 0;
}

The end.