题意分析

本题是经典的双调欧几里得旅行商问题（Bitonic Euclidean Traveling Salesman Problem）[3][5][7]：

• 给定平面中 n 个点（按 x 坐标升序排列）
• 从最左点出发，严格向右走到最右点（x 递增）
• 再从最右点严格向左返回起点（x 递减）
• 求解最短闭合路径（覆盖所有点）

关键约束：

• 路径分为两部分：从左到右的递增路径 + 从右到左的递减路径
• 点不能重复访问（除起点/终点外）
• 利用双调路径特性将 NP 难问题简化为 O(n²) 动态规划

解题思路

1. 预处理：

   • 读取按 x 排序的点（题目已保证有序）
   • 预计算每两点间的欧氏距离

2. 动态规划（参考双调路径算法[3][4][7]）：

   • 定义 dp[i][j]（i > j）：
     • 表示一条路径到达点 i，另一条路径到达点 j
     • 覆盖了从点 0 到点 i 的所有点
   • 状态转移：
     • 情况1（i > j+1）：dp[i][j] = dp[i-1][j] + dist(i-1, i) 直接延续右侧路径
     • 情况2（i = j+1）：dp[i][j] = minₖ {dp[j][k] + dist(k, i)} 枚举左侧路径的转折点
   • 初始化：
     • dp[1][0] = dist(0, 1)（仅两个点时）

3. 最终答案：

   • ans = minⱼ {dp[n-1][j] + dist(j, n-1)}
   • 解释：将两条路径连接至最右点并形成回路[4]

代码实现（C++）

#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

const int MAXN = 1010;
double dp[MAXN][MAXN], dist[MAXN][MAXN];
int n;

struct Point { double x, y; } pts[MAXN];

inline double calcDist(Point& a, Point& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
}

int main() {
    while (cin >> n) {
        // 读取点（已按x排序）
        for (int i = 0; i < n; ++i)
            cin >> pts[i].x >> pts[i].y;

        // 边界情况处理
        if (n == 1) {
            cout << "0.00\n";
            continue;
        }
        if (n == 2) {
            double d = calcDist(pts[0], pts[1]);
            cout << fixed << setprecision(2) << 2*d << '\n';
            continue;
        }

        // 预计算距离
        for (int i = 0; i < n; ++i)
            for (int j = i+1; j < n; ++j)
                dist[i][j] = dist[j][i] = calcDist(pts[i], pts[j]);

        // 初始化DP
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                dp[i][j] = 1e18;
        dp[1][0] = dist[1][0];  // 初始状态：0->1

        // DP过程
        for (int i = 2; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (j == i-1) {  // 情况2
                    for (int k = 0; k < j; ++k)
                        dp[i][j] = min(dp[i][j], dp[j][k] + dist[k][i]);
                } else {  // 情况1
                    dp[i][j] = dp[i-1][j] + dist[i-1][i];
                }
            }
        }

        // 计算最终答案
        double ans = 1e18;
        for (int j = 0; j < n-1; ++j)
            ans = min(ans, dp[n-1][j] + dist[j][n-1]);
        
        cout << fixed << setprecision(2) << ans << '\n';
    }
    return 0;
}

代码说明

1. 精度处理：

   • 使用 double 存储距离和小数
   • 输出时通过 setprecision(2) 保留两位小数

2. 边界处理：

   • n=1 时路径长度为0
   • n=2 时路径为往返距离的2倍

3. 复杂度：

   • 时间：O(n²)
   • 空间：O(n²)
   • 适用于 n ≤ 1000 的规模（题目未指定，但参考[4][7]实现）

4. 关键优化：

   • 距离矩阵预计算避免重复开方
   • 严格遵循双调路径特性进行状态转移[3][8]