c/c++语言开发共享洛谷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); }