题解：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++

CPP

#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;
}

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

文章操作

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

思路简述

代码呈现

C++

The end.

相关推荐

评论

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