UVA - 1347 Tour（雙調旅行商問題）

​​UVA - 1347 Tour​​

題目

旅行商問題描述：平面上n個點，确定一條連接配接各點的最短閉合旅程。

題目按照x遞增順序給出，各點x不同。

分析

動态規劃

題目說從最左端走到最右端，再傳回最左端。可以想象成兩個人同時從最左端沿着兩條不同路徑走到最右端，保證每個點走到一次，則他們兩個的路徑相加最短就是答案。

最難的就是定義狀态，狀态定義的好壞直接影響題目的解決

将題目給出的點按 x 大小編号 1 到 n，

用

表示

的點都已經走過，而且目前位置是

，還需要至少多少距離。顯然，最後要求的答案就是

。

思考狀态轉移方程，

因為

，是以dp數組隻需要填一半就行，不妨規定

，下一次隻能走到

，那麼

因為

方程變為

遞推

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;

int n;
double dp[N][N];    //表示 1~max(i,j) 已經走過，現在在位置（i，j），最少還要多少距離
double x[N], y[N], dis[N][N];

int main()
{
    while(cin >> n){
        for(int i = 1; i <= n; i++){
            scanf("%lf%lf", &x[i], &y[i]);
        }
        for(int i = 1; i <= n; i++){    //預處理所有點之間距離
            for (int j = 1; j <= n; j++){
                dis[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
            }
        }

        for (int i = n - 1; i >= 1; i--){
            for (int j = 1; j <= i; j++){
                if(i == n-1){
                    dp[i][j] = dis[i][n] + dis[j][n];   //邊界 兩人直接走到終點
                }else{
                    dp[i][j] = min(dis[i][i + 1] + dp[i + 1][j], dis[j][i + 1] + dp[i + 1][i]);
                }
            }
        }
        printf("%.2f\n", dp[1][1]);
    }
    return 0;
}      

記憶化搜尋

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;

int n;
double dp[N][N];    //表示 1~max(i,j) 已經走過，現在在位置（i，j），最少還要多少距離
double x[N], y[N], dis[N][N];

double DP(int i, int j)
{
    double &ans = dp[i][j];
    if(ans > 0)         //已經求過
        return ans;
    if(i == n-1){
        ans = dis[n - 1][n] + dis[j][n];
    }else{
        ans = min(dis[i][i + 1] + DP(i + 1, j), dis[j][i + 1] + DP(i + 1, i));
    }
    return ans;
}

int main()
{
    while(cin >> n){
        for(int i = 1; i <= n; i++){
            scanf("%lf%lf", &x[i], &y[i]);
        }
        for(int i = 1; i <= n; i++){    //預處理所有點之間距離
            for (int j = 1; j <= n; j++){
                dp[i][j] = -1.0;
                dis[i][j] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
            }
        }
        printf("%.2f\n", DP(1, 1));
    }
    return 0;
}