题目大意

在周长为 $L$ 的环形湖泊周围有 $N$ 个邮票收集点，第 $i$ 个收集点位于从起点顺时针 $X_i$ 米的位置。参赛者从起点出发，每秒移动 $1$ 米，可以顺时针或逆时针移动。要收集第 $i$ 张邮票，必须在比赛开始后 $T_i$ 秒内到达其收集点。求最多能收集到多少种邮票。

问题分析

关键观察

1. 环形结构：湖泊是环形的，需要考虑两个移动方向。
2. 时间限制：每个邮票有独立的收集时间窗口。
3. 移动策略：最优策略通常是先向一个方向收集若干邮票，然后转向另一个方向。

核心思路

这是一个典型的环形路径上的最优收集问题，可以使用动态规划解决。

算法设计

状态设计

定义四维 DP 状态： dp[l][r][i][0/1] 表示：

• 从左侧（逆时针方向）收集了 l 张邮票
• 从右侧（顺时针方向）收集了 r 张邮票
• 总共收集了 i 张邮票
• 当前位于左端点(0)或右端点(1) 状态值表示达成该状态所需的最小时间。

状态转移

对于每个状态 (l, r, i, pos)，考虑两种移动：

1. 继续当前方向：

   • 如果当前位置是左端点(0)，则向左移动收集下一张邮票
   • 如果当前位置是右端点(1)，则向右移动收集下一张邮票

2. 转向另一方向：

   • 如果当前位置是左端点(0)，转向右端收集邮票
   • 如果当前位置是右端点(1)，转向左端收集邮票

转移方程

设当前位置为 pos：

• 继续原方向：移动到相邻收集点，时间增加两点间距离
• 转向另一方向：沿环形路径移动到另一侧的收集点，时间增加环形路径长度减去当前跨度

在每次移动时检查：

• 如果到达时间 ≤ 目标邮票的 $T_i$，则可以收集该邮票（i + 1）
• 否则不能收集（i 不变）

初始化

• dp[0][0][0][0] = dp[0][0][0][1] = 0
• 其他状态初始化为无穷大

最终答案

遍历所有可能的 (l, r, i, pos) 状态，找到最大的 i 使得 dp[l][r][i][pos] 不为无穷大。

算法细节

环形处理技巧

• 将环形展开，邮票位置按顺时针排序
• 左侧收集从位置 n, n-1, ... 逆序收集
• 右侧收集从位置 1, 2, ... 顺序收集
• 使用环形周长 L 计算转向时的路径长度

时间复杂度

• 状态数：$O(N^3)$（l, r, i 各 $N$ 级别）
• 每个状态 $O(1)$ 转移
• 总复杂度：$O(N^3)$，对于 $N \leq 200$ 可接受

空间复杂度

• 四维 DP 数组：$O(N^3)$

实现要点

1. 坐标处理：将邮票位置排序，处理环形坐标
2. 边界情况：考虑 $N=0$ 和所有 $T_i=0$ 的情况
3. 状态转移：仔细计算两个方向的移动时间和距离
4. 答案统计：在所有可达状态中寻找最大收集数量

总结

本题是环形路径上的最优收集问题，通过四维动态规划状态记录左右两侧收集情况和当前位置，巧妙地处理了环形结构和时间约束。算法的核心在于状态设计和转移方程的精确计算，体现了动态规划在复杂约束条件下的强大建模能力。