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

· · 题解

题目传送门：P8733 [蓝桥杯 2020 国 C] 补给。

前言

蒟蒻自认为自己很菜，这是个人认为和我一样的蒟蒻看得懂的题解

前置芝士

题目大意

给定 n 个点的坐标和整数 D。求一条起点为第一个点，不重不漏地经过每一个点，最后回到第一个点使得路径最小。该路径上的每一段距离不能超过 D。

题目分析

首先要注意题目中有这么一句话：

1 \le n \le 20

状压,启动！
然后还有就是由于

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

所以导致题目中的给的两点之间线段最短的公式可能超过 D 的范围，所以我们要先求出最短路小于 D 的路径，否则设为无限大。

状压实现

由于有走过和没走过之分，所以要用到位运算，具体实现可看代码。

状态转移方程：


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

警钟长鸣

1、记得开 double；

2、得数要保留 2 位小数。

Accoder

杜绝抄袭，从我做起。

#include<bits/stdc++.h>
using namespace std;
double dis[25][25],dp[(1<<20)+5][25];
int n,D;
struct node{
    int x,y;
}a[25];
int main(){
    cin>>n>>D;
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i].x >> a[i].y; //平平无奇的输入 
    }
    for(int i = 1 ; i <= n ; ++i){//找出题中所给的最短路 
        for(int j = 1 ; j <= n ; ++j){
            double d=sqrt((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y));
            if (d <= D){
                dis[i][j] = d;
            }
            else{
                dis[i][j] = 1e10;
            }
        } 
    }
    //弗洛伊德
    for(int i = 1 ; i <= n ; i++){//标准模版 
        for(int j = 1 ; j <= n ; j++){
            for(int k = 1 ; k <= n ; k++){
                dis[j][k] = min(dis[j][k],dis[j][i] + dis[i][k]);
            }
        }
    }
    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 k = 1 ; k <= n ; ++k){
                    if(j != k && (i & (1 << (k - 1)))){
                        if(j != k && (i & ( 1 << (k - 1)))){
                            dp[i][j] = min (dp[i][j],dp[i ^ (1 << j - 1)][k] + dis[k][j]);
                        }
                    }
                }
            }
        }
    }
    double ans=1e15;//寻找答案 
    for(int i = 1 ; i <= n ; i++){
        ans=min(ans,dp[(1 << n) - 1][i] + dis[i][1]);   
    }
    printf("%.2lf",ans);//平平无奇的输出 
    return 0;
}

双倍经验

最后给道相似的题目。

完结撒花


#include<bits/stdc++.h>
using namespace std;
string a[205],t;
int cnt;
string add(string str1,string str2){
    string str;
    int len1=str1.length();
    int len2=str2.length();
    if(len1<len2)
    {
        for(int i=1;i<=len2-len1;i++)
            str1="0"+str1;
    }
    else
    {
        for(int i=1;i<=len1-len2;i++)
            str2="0"+str2;
    }
    len1=str1.length();
    int cf=0;
    int temp;
    for(int i=len1-1;i>=0;i--)
    {
        temp=str1[i]-'0'+str2[i]-'0'+cf;
        cf=temp/10;
        temp%=10;
        str=char(temp+'0')+str;
    }
    if(cf!=0)  str=char(cf+'0')+str;
    return str;
}
string mul(string str1,string str2)
{
    string str;
    int len1=str1.length();
    int len2=str2.length();
    string tempstr;
    for(int i=len2-1;i>=0;i--)
    {
        tempstr="";
        int temp=str2[i]-'0';
        int t=0;
        int cf=0;
        if(temp!=0)
        {
            for(int j=1;j<=len2-1-i;j++)
                tempstr+="0";
            for(int j=len1-1;j>=0;j--)
            {
                t=(temp*(str1[j]-'0')+cf)%10;
                cf=(temp*(str1[j]-'0')+cf)/10;
                tempstr=char(t+'0')+tempstr;
            }
            if(cf!=0) tempstr=char(cf+'0')+tempstr;
        }
        str=add(str,tempstr);
    }
    str.erase(0,str.find_first_not_of('0'));
    return str;
}
int main(){
    a[1]="1";
    t="3";
    cin>>cnt;
    for(int i=2;i<=cnt+1;i++){
        a[i]=mul(a[i-1],"9");
        a[i]=add(a[i],t);
        t=mul(t,"4");
    }
    cout<<a[cnt+1];
    return 0;
}