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

· · 题解

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