「春季测试 2023」圣诞树 题解

题目大意

给定一个凸多边形的 $n$ 个顶点坐标，需要找到从最高点 $k$ 出发，经过所有顶点恰好一次的最短路径（哈密顿路径）。

解题思路

核心算法：区间动态规划

该解法使用区间DP来求解凸多边形上的最短哈密顿路径，利用凸多边形的性质来设计高效算法。

关键数据结构

struct point {
    double x, y;
} p[N], tp[N];  // 存储顶点坐标

double f[N][N][2];  // DP数组，f[l][r][pos]表示区间[l,r]的最短路径长度
int g[N][N][2];     // 记录路径选择
int id[N];          // 重编号后的实际顶点编号

算法流程

1. 找到最高点 $k$

int k = 0;
double Y = -1e9;
for (int i = 1; i <= n; ++i) {
    cin >> tp[i].x >> tp[i].y;
    if (tp[i].y > Y)
        k = i, Y = tp[i].y;
}

2. 顶点重编号

for (int i = 1; i <= n - k; ++i)
    p[i] = tp[i + k], id[i] = i + k;
for (int i = n; i > n - k; --i)
    p[i] = tp[i - n + k], id[i] = i - n + k;

• 将最高点 $k$ 放在序列的末尾（位置 $n$）
• 其他点按原顺序重新排列
• 这样DP时可以从最高点向两边扩展

3. 动态规划求解

void Dp() {
    for (int len = 2; len < n; ++len)
        for (int l = 1; r < n; ++l) {
            // 状态转移计算
        }
}

状态定义：

• f[l][r][0]：当前路径覆盖区间 $[l, r]$，且当前在左端点 $l$ 的最短路径长度
• f[l][r][1]：当前路径覆盖区间 $[l, r]$，且当前在右端点 $r$ 的最短路径长度

状态转移：

double disll = f[ad(l)][r][0] + dis(l, ad(l));  // 从l+1扩展到l
double dislr = f[ad(l)][r][1] + dis(l, r);     // 从r扩展到l
double disrl = f[l][p(r)][0] + dis(l, r);      // 从l扩展到r  
double disrr = f[l][p(r)][1] + dis(p(r), r);   // 从r-1扩展到r

4. 路径输出

void print(int l, int r, int pos) {
    cout << (pos ? id[r] : id[l]) << ' ';
    if (l == r) return;
    if (pos)
        print(l, p(r), g[l][r][pos]);
    else
        print(ad(l), r, g[l][r][pos]);
}

算法原理

为什么这样设计？

1. 凸多边形性质：在凸多边形上，最短哈密顿路径不会自交
2. 区间DP思想：从最高点开始，逐步向两边扩展路径
3. 状态设计：记录当前覆盖的区间和当前位置，便于状态转移

关键观察

对于凸多边形上的最短路径问题：

• 路径可以看作在环形序列上选择一个起点，然后向两边扩展
• 每次扩展时，只能选择相邻的未访问顶点
• 使用区间DP可以高效求解

复杂度分析

• 时间复杂度：$O(n^2)$
  • 双重循环：$O(n^2)$
  • 每个状态转移：$O(1)$
• 空间复杂度：$O(n^2)$

样例验证

样例1：

顶点坐标：
1: (0,0), 2: (3,0), 3: (1,1) ← 最高点k=3

重编号后：
p[1] = 点1, p[2] = 点2, p[3] = 点3
id[1] = 1, id[2] = 2, id[3] = 3

DP过程计算得到最优路径：3→1→2

代码亮点

1. 重编号技巧：将最高点放在序列末尾，简化DP过程
2. 状态设计：使用三维状态记录区间和当前位置
3. 路径记录：在DP过程中记录最优选择，便于最终输出
4. 精度控制：使用 long double 提高计算精度

实现细节

宏定义说明

#define p(x) (x - 1)     // 前一个位置
#define ad(x) (x + 1)    // 后一个位置  
#define sr(x) ((x) * (x)) // 平方

距离计算

inline double dis(int px, int py) {
    return sqrtl(sr(p[px].x - p[py].x) + sr(p[px].y - p[py].y));
}

• 使用 long double 和 sqrtl 保证精度
• 直接计算欧几里得距离

总结

这个解法通过巧妙的区间DP设计，高效解决了凸多边形上的最短哈密顿路径问题。核心创新点：

1. 重编号策略：将最高点置于序列末端，简化状态转移
2. 三维状态：同时记录覆盖区间和当前位置
3. 路径重建：在DP过程中记录选择，便于最终输出路径

该算法能够处理中等规模的凸多边形最短路径问题，是一个典型且高效的几何动态规划解决方案。