洛谷P1523 旅行商简化版(DP)

题目：

P1523 旅行商简化版

解析

可以看做是两个人同时从西往东走，经过不一样的点，走到最东头的方案数

设\(f[i][j]\)表示一个人走到i，一个人走到j的最短距离（\(i<j\)）

第\(j+1\)个位置，两个人都可能走，两种情况

\(f[i][j+1]=min\{f[i][j+1],f[i][j]+dis[j][j+1]\}\)位置在j的人走到了j+1位置
\(f[j][j+1]=min\{f[j][j+1],f[i][j]+dis[i][j+1]\}\)位置在i的人走到了j+1位置

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;

double f[N][N], dis[N][N];

struct node {

    double x, y;

    bool operator <(const node &oth) const {

        return x < oth.x;

    }

} e[N];

double calc(node a, node b) {

    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));

}

int main() {

    ios::sync_with_stdio(false);

    cin >> n;

    for (int i = 1; i <= n; ++i)

        cin >> e[i].x >> e[i].y;

    sort(e + 1, e + 1 + n);

    for (int i = 1; i <= n; ++i)

        for (int j = i + 1; j <= n; ++j)

            dis[i][j] = calc(e[i], e[j]), f[i][j] = LLONG_MAX;

    f[1][2] = dis[1][2];

    for (int i = 1; i <= n; ++i)

        for (int j = i + 1; j <= n; ++j) {

            f[i][j + 1] = min(f[i][j + 1], f[i][j] + dis[j][j + 1]);

            f[j][j + 1] = min(f[j][j + 1], f[i][j] + dis[i][j + 1]);

        }

    double ans = LLONG_MAX;

    for (int i = 1; i < n; ++i) ans = min(ans, f[i][n] + dis[i][n]);

    printf("%.2lf", ans);

}

巴特西

洛谷P1523 旅行商简化版(DP)

最新文章

热门文章