首先按横坐标递增给所有点排序。
定义状态dp[i][j]表示从点i向n走一条路L1，从点j向n走另一条路L2（如下图，两条路互不相交，并且L1在L2上面），L1 + L2的最小值。程序中用distance(i, j)表示点i到点j的距离。
如何计算dp[i, j]呢?
我们考虑k = max(i, j) + 1这个点，这个点肯定在L1或者L2上。
k在L1上时，如下图
k在L2上时，如下图
dp[i][j]取这两者最小值即可。
可能还是有点抽象，举个实际的例子吧。
假如i = 5, j = 4。在计算dp[5][4]的时候，考虑6这个点。6只有两种选择，要么在L1上（上面的路），这时候的代价为dp[6][4] + distance(5, 6)。要么在L2上（下面的路），这时候的代价为dp[5][6] + distance(4, 6)。
所以状态转移方程为：dp[i][j] = min(dp[i][k] + distance(j, k),dp[k][j] + distance(i, k))
一、临界情况
1. i = n: dp[i][j] = distance(j, n)
2. j = n: dp[i][j] = distance(i, n)
二、其余情况
k = max(i, j) + 1
dp[i][j] = min(dp[i][k] + distance(j, k), dp[k][j] + distance(i,k))
代码如下：
#include <cmath> #include <ctime> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; const int MAX_SIZE = 200; double dp[MAX_SIZE][MAX_SIZE]; struct Coordinate { double x, y; bool operator < (const Coordinate& b) { return x < b.x; } }; Coordinate co[MAX_SIZE]; double distance(int i, int j) { return sqrt((co[i].x - co[j].x) * (co[i].x - co[j].x) + (co[i].y - co[j].y) * (co[i].y - co[j].y)); } int main() { //freopen("1.txt", "r", stdin); int n; while (cin >> n) { for (int i = 1; i <= n; i++) scanf("%lf%lf", &co[i].x, &co[i].y); sort(co + 1, co + n + 1); memset(dp, 0, sizeof(dp)); for (int i = n; i >= 1; i--) for (int j = n; j >= 1; j--) { if (i == n && j == n) dp[i][j] = 0; else if (j == n) dp[i][j] = distance(i, n); else if (i == n) dp[i][j] = distance(j, n); else { int k = max(i, j) + 1; dp[i][j] = min(dp[i][k] + distance(j, k), dp[k][j] + distance(i, k)); } } printf("%.2f\n", dp[1][1]); } return 0; }
