欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥杯 算法提高 ADV-277 The Islands(记录转移的简单动态规划)

程序员文章站 2022-07-15 12:28:44
...

题目大意:

二维平面上有n个点,每个点的坐标是整数,其中有两个特殊点A和B,现在把所有的点按照x坐标从小到大排序,要求一条从起点S到终点T再回到S的最短路径,要求每个点都要经过一次,并且在从S到T的过程中x坐标只能单增,从T回到S过程中x坐标只能单减。A点和B点要分别在去和回来的路上。要计算出最短路径长度,并输出路径。

思路:

假设节点从 11 号点到 nn 号点 xx 坐标依次增加。问题就等价于从 11 号点到 nn 号点找到两条没有公共节点的路径,两个路径分别经过 AA 点和 BB 点,求两条路径长度的和最短。
dp(i,j)dp(i,j) 表示从 11 号点第一条路径到 ii 号点,第二条路径到 jj 号点的两条路径的最短距离和。
那么对于 dp(i,j)dp(i,j) ,如果 i>ji>j ,那么下一个要决策的点就是 i+1i+1 号点,这个点可以有两种方式,第一种是放到第一条路径上,那么 dp(i,j)dp(i,j) 就转移到了 dp(i+1,j)dp(i+1,j) 上;第二种是放到第二条路径上,那么就转移到了 dp(i,i+1)dp(i,i+1) 状态上。如果 i<ji<j ,那么下一个要决策的点就是 j+1j+1 号点,这个点也可以有两种方式,第一种是放到第一条路径上,那么 dp(i,j)dp(i,j) 就转移到了 dp(j+1,j)dp(j+1,j) 上面;如果是放到第二条路径上,那么就是转移到 dp(i,j+1)dp(i,j+1) 状态上。

下面只要依次枚举每个状态,然后向后进行转移就可以了,这里注意对于 AA 节点和 BB 节点一定要设计转移,我们不妨假设 AA 点一定在第一条路径上,BB 点一定在第二条路径上,这样就可以在转移之前先进行一个判断,就可以保证最后的答案一定是 AABB 在不同的路径上。此外转移的时候用 prepre 数组记一下上一个状态就可以从最后的状态一点点回溯会初始状态,也就知道了两个最短的路径的形式。

代码:

/*
2019-12-26 17:34:11
from xcx
个人博客地址:https://blog.csdn.net/qq_36306833
欢迎交流学习
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 104;
struct point{
    int x, y;
    point(){}
    point(int xx, int yy){
        this->x = xx;
        this->y = yy;
    }
}a[maxn],pre[maxn][maxn];

int inline p2(int x){return x*x;}
inline double dis(point a, point b){
    return sqrt(p2(a.x- b.x) + p2(a.y- b.y));
}

int n, m1, m2;
double dp[maxn][maxn];
bool vis[maxn][maxn];
int main(){
    int cas = 1;
    while(scanf("%d%d%d",&n,&m1,&m2)!=EOF){
        if(n==0 && m1==0 && m2==0){
            break;
        }
        m1++, m2++;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a[i].x, &a[i].y);
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                vis[i][j] = false;
                dp[i][j] = 1e10;
            }
        }
        dp[1][1] = 0;
        for(int i=1;i<n;i++){
            for(int j=1;j<n;j++){
                if(i!=1 && i == j)continue;
                if(i >= j){ // i+1的去哪
                    // dp[i][j] -> dp[i+1][j] = dp[i][j]+dis(i,i+1)  dp[i][i+1] = dp[i][j]+dis(j,i+1)
                    if(i+1!=m2 && (vis[i+1][j] == false || dp[i+1][j] > dp[i][j] + dis(a[i], a[i+1]))){
                        pre[i+1][j] = point(i, j);
                        vis[i+1][j] = true;
                        dp[i+1][j] = dp[i][j] + dis(a[i], a[i+1]);
                        // printf("%d %d -> %d %d (1)\n",i,j,i+1,j);
                    }
                    if(i+1!=m1 && (vis[i][i+1] == false || dp[i][i+1] > dp[i][j] + dis(a[j], a[i+1]))){
                        pre[i][i+1] = point(i, j);
                        vis[i][i+1] = true;
                        dp[i][i+1] = dp[i][j] + dis(a[j], a[i+1]);
                        // printf("%d %d -> %d %d (2)\n",i,j,i,i+1);
                    }
                }
                if(i <= j){ // j+1的去哪
                    // dp[i][j] -> dp[i][j+1] = dp[i][j]+dis(j,j+1)  dp[j+1][j] = dp[i][j]+dis(i,j+1)
                    if(j+1!=m1 && (vis[i][j+1] == false || dp[i][j+1] > dp[i][j] + dis(a[j], a[j+1]))){
                        pre[i][j+1] = point(i, j);
                        vis[i][j+1] = true;
                        dp[i][j+1] = dp[i][j] + dis(a[j], a[j+1]);
                        // printf("%d %d -> %d %d (3)\n",i,j,i,j+1);
                    }
                    if(j+1!=m2 && (vis[j+1][j] == false || dp[j+1][j] > dp[i][j] + dis(a[i], a[j+1]))){
                        pre[j+1][j] = point(i, j);
                        vis[j+1][j] = true;
                        dp[j+1][j] = dp[i][j] + dis(a[i], a[j+1]);
                        // printf("%d %d -> %d %d (4)\n",i,j,j+1,j);
                    }
                }
            }
        }
        /*for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                printf("dp[%d][%d] = %15.2f  ",i,j,dp[i][j]);
            }
            printf("\n");
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                printf("pre[%d][%d] = (%d, %d)  ",i,j,pre[i][j].x, pre[i][j].y);
            }
            printf("\n");
        }*/
        double ans = 1e20;
        int posx = -1, posy = n;
        for(int i=1;i<=n;i++){
            if(i == m2)continue;
            if(ans > dp[i][n]+ dis(a[i], a[n])){
                ans = dp[i][n]+ dis(a[i], a[n]);
                posx = i;
            }
        }
        vector<int> way1, way2;
        while(posx != 0 && posy != 0){
            //printf("%d %d ->",posx,posy);
            if(pre[posx][posy].x != posx){
                way1.push_back(posx);
                posx = pre[posx][posy].x;
            }
            else{
                way2.push_back(posy);
                posy = pre[posx][posy].y;
            }
        }
        vector<int> xcx;
        printf("Case %d: %.2f\n", cas++, ans);
        for(int i=way1.size()-1;i>=0;i--){
            xcx.push_back(way1[i]-1);
        }
        for(int i=0;i<way2.size();i++){
            xcx.push_back(way2[i]-1);
        }
        xcx.push_back(0);
        if(xcx[1] != 1){
            reverse(xcx.begin(), xcx.end());
        }
        for(int i=0;i<xcx.size();i++){
            if(i!=0){
                printf(" ");
            }
            printf("%d",xcx[i]);
        }
        printf("\n");
    }
    return 0;
}