「蓝桥杯 2020 国 C」补给 解题记录

P8733 [蓝桥杯 2020 国 C] 补给

题意简述

给定平面直角坐标系的 $n$ 个点和一个整数 $D$ ，求从节点 $1$ 遍历所有的 $n$ 个点再回到节点 $1$ 的最短路径。路径上任意两个节点的欧几里得距离不能超过 $D$ 。

题目分析

先看数据范围，$1\le n\le 20$，考虑状压。
对于这种与路径长度有关的状压DP，我们通常设 d p S , j dp_{S,j}dpS,j​ 为状态集合为 $S$ 时，当前在节点 $j$ 时的最短路径长度（因为路径的长度与两个节点相关，所以可以记录一个节点，枚举一个节点，故设一维保存节点）。状态转移方程：
d p S∪{j},j ←mi n k=0nd p S,k +di s k,j dp_{S \cup \{j\},j} \gets min_{k=0}^{n}dp_{S,k}+dis_{k,j} dpS∪{j},j​←mink=0n​dpS,k​+disk,j​
其中 d i s k , j dis_{k,j}disk,j​ 表示从 $k$ 到 $j$ 的距离。
但是这道题有点不一样，因为它还有一个限制条件，在两个节点的路径长度大于 $D$ 的时候是不能转移的，这个时候我们只能考虑使一个另外的节点充当“中转站”，再从“中转站”转移到目标节点。于是便有了这份暴力代码：

CI N=20;double calc(double x1,double y1,double x2,double y2) {return std::sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}int n,d;PII id[N];double dp[1<<N][N],dis[N][N],ans=0x3f3f3f3f;signed main() {std::cin>>n>>d;rep(i,1,n) {std::cin>>id[i].ff>>id[i].ss;}rep(i,1,n) {rep(j,1,n) {dis[i][j]=calc(id[i].ff,id[i].ss,id[j].ff,id[j].ss);}}rep(i,0,(1<<20)-1) {rep(j,1,N-1) {dp[i][j]=1e9;}}dp[1][1]=0;rep(i,1,(1<<n)-1) {rep(j,1,n) {if((i>>j-1)&1) {continue;}rep(k,1,n) {if(k==j) {continue;}if(dis[k][j]>d) {rep(l,1,n) {if(dis[k][l]>d||dis[l][j]>d) {continue;}dp[i|(1<<j-1)][j]=std::min(dp[i|(1<<j-1)][j],dp[i][k]+dis[k][l]+dis[l][j]);}} else {dp[i|(1<<j-1)][j]=std::min(dp[i|(1<<j-1)][j],dp[i][k]+dis[k][j]);}}}}rep(i,1,n) {if(dis[i][1]>d) {rep(j,1,n) {if(dis[i][j]>d||dis[j][1]>d) {continue;}ans=std::min(ans,dp[(1<<n)-1][i]+dis[i][j]+dis[j][1]);}} else {ans=std::min(ans,dp[(1<<n)-1][i]+dis[i][1]);}}printf("%.2lf",ans);return 0;}

结果当然是

算法优化

这份代码的时间复杂度为 O ( 2nn3) ≈ 1 09 O(2^nn^3) \approx 10^9O(2nn3)≈109 ，所以我们考虑优化。
造成时间复杂度如此之高的原因是在 DP 转移的时候多次判断了路径长度是否超过 $D$ ，造成重复计算，所以我们可以把 dis[N][N] 预处理出来，与 DP 转移的分开处理，时间复杂度为 O ( 2nn2)O(2^nn^2)O(2nn2) ，可以通过此题

AC Code

CI N=25;double calc(int x1,int y1,int x2,int y2) {return std::sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}int n,d;PII id[N];double dp[1<<20][N],dis[N][N],ans=0x3f3f3f3f;signed main() {rep(i,0,(1<<18)-1) {rep(j,1,N) {dp[i][j]=1e9;}}std::cin>>n>>d;rep(i,1,n) {std::cin>>id[i].ff>>id[i].ss;}rep(i,1,n) {rep(j,1,n) {dis[i][j]=1e9;}}rep(i,1,n) {rep(j,1,n) {if(calc(id[i].ff,id[i].ss,id[j].ff,id[j].ss)>d) {rep(k,1,n) {if(calc(id[i].ff,id[i].ss,id[k].ff,id[k].ss)>d||calc(id[k].ff,id[k].ss,id[j].ff,id[j].ss)>d) {continue;}dis[i][j]=std::min(dis[i][j],calc(id[i].ff,id[i].ss,id[k].ff,id[k].ss)+calc(id[k].ff,id[k].ss,id[j].ff,id[j].ss));}} else {dis[i][j]=calc(id[i].ff,id[i].ss,id[j].ff,id[j].ss);}}}rep(i,0,(1<<20)-1) {rep(j,1,N-1) {dp[i][j]=1e9;}}dp[1][1]=0;rep(i,1,(1<<n)-1) {rep(j,1,n) {if((i>>j-1)&1) {continue;}rep(k,1,n) {if(k==j) {continue;}if(!((i>>k-1)&1)) {continue;}dp[i|(1<<j-1)][j]=std::min(dp[i|(1<<j-1)][j],dp[i][k]+dis[k][j]);}}}rep(i,1,n) {ans=std::min(ans,dp[(1<<n)-1][i]+dis[i][1]);}printf("%.2lf",ans);return 0;}