平面 n 點，求最短閉合雙調旅程：從最左點嚴格左→右至最右點，再嚴格右→左返回起點。點按 x 座標排序後，動態規劃 O(n²) 求解。
設點按 x 升序編號 1..n。dp[i][j] (i > j) 表示兩條路徑分別到達 i 和 j，且已覆蓋 1..i 所有點的最小長度。其中一條路徑必在 i（最右），另一條在 j。
dp[i][j] = dp[i-1][j] + dist(i, i-1)dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dist(j, i)) 對所有 j < i-1 取最小答案：min(dp[n][n-1] + dist(n-1,n), min_{j
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define INF 1e20
const int N = 105;
int n; double x[N], y[N], dp[N][N];
double dis(int i, int j) {
return sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
}
int main() {
while (~scanf("%d", &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] = INF;
dp[2][1] = dis(2, 1);
for (int i = 3; i <= n; i++) {
dp[i][i-1] = INF;
for (int j = 1; j < i-1; j++) {
dp[i][j] = dp[i-1][j] + dis(i, i-1);
dp[i][i-1] = std::min(dp[i][i-1], dp[i-1][j] + dis(j, i));
}
}
double ans = dp[n][n-1] + dis(n-1, n);
for (int j = 1; j < n-1; j++) ans = std::min(ans, dp[n][j] + dis(j, n));
printf("%.2lf\n", ans);
}
return 0;
}
dp[2][1] 為兩點直連。
