P8733 [蓝桥杯 2020 国 C] 补给 题解

· · 题解

保姆级题解，站在我的角度看，保证 xxs 也能懂。

如果只是为了代码而看，可以直接跳到最后面复制，后果自负。

题目传送门

算法分析

根据算法标签和数据范围，我们可以知道这是一道状压 DP。

前置芝士

限于篇幅，不会自行百度。

思路

1.预处理

首先，我们可以预处理各个点之间的最短距离。

因为题目中有这句话：

小蓝单次飞行的距离不能超过 D。

所以不能直接用题目中给的距离公式求出所有距离。

可以先把满足 \sqrt{(x_i-x_j)^2+(y_i-y_j)^2} \le D 的点用公式求出来，然后用 Floyd 跑一遍最短路。

upd on 2024.1.5：如果两个点不能联通，则把 dis_{i,j} 设为无限。

2.状压求解

分析

由于每一个城市都有走过和没走过两种状态，可以把走过城市对应的二进制位设为 1，把没走过的设为 0。

这里又有一个问题：因为我们要从前一个路径方案的终点来推，但现在我们只能知道已经走过的城市，所以该怎么办？

再设一维嘛！

可以得出 dp_{i,j} 表示本路径方案城市状态为 i，终点为 j 时的最短路径。

求解

首先，因为 dp_{i,j} 表示最短路径，为了后面进行取最小值操作，先把整个 dp 数组赋值为 1 \times 10^{10}（其实只要是一个很大的数就行）。

考虑到小蓝从总部出发（编号为 1 的村庄），所以把 dp_{1,1} 设为 0，因为最开始没出发的时候还没有走（距离为 0）。

再枚举

来推转移方程。

这里需要两次特判：

转移方程

dp[i][j]=min(dp[i][j],dp[i^(1<<j-1)][d]+dis[d][j]

upd on 2023.11.11：

解释一下，dp_{i,j} 是由上一种不包含这次路径的终点城市得来的，所以要异或上 (1<<j-1)，因为异或这里可以把 1 变成 0。

最后从经过所有城市的路径加上终点和编号为 1 的村庄的距离中选一个最小值，得解。

注意事项

\color{#52C41A}\texttt{AC} \texttt{Code}

#include<bits/stdc++.h>
using namespace std;
double dp[(1<<20)+5][25],dis[25][25],a[25],b[25];
int n,D;
int main(){
    cin>>n>>D;
    for(int i=1;i<=n;++i){
        cin>>a[i]>>b[i];
    }for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            double d=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));
            if(d<=D) dis[i][j]=d;
            else dis[i][j]=1e10;
        }
    }
    //Floyd 板子
    for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    for(int i=0;i<(1<<n);++i){
        for(int j=1;j<=n;++j){
            dp[i][j]=1e10;
        }
    }
    dp[1][1]=0;
    for(int i=0;i<(1<<n);++i){
        for(int j=1;j<=n;++j){
            if((i&(i<<(j-1)))){
                for(int d=1;d<=n;++d){
                    if(j!=d&&(i&(1<<(d-1))))dp[i][j]=min(dp[i][j],dp[i^(1<<j-1)][d]+dis[d][j]);
                }
            }
        }
    }double ans=1e13;
    for(int i=1;i<=n;++i){
        ans=min(ans,dp[(1<<n)-1][i]+dis[i][1]);
    }printf("%.2lf",ans);
    return 0;
}