列车与统计 题解

思路

令 $dp_i=\sum_{j=i+1}^n\rho_{i,j}$。若 $a_i=n$，显然 $dp_i=n-i$。

否则在区间 $[i+1,a_i]$ 中选取 $a_p$ 最大的位置 $p$。由于该区间包含位置 $a_i$，有 $a_p>a_i$。对所有 $j>a_i$，最优路线可以先花一元到达 $p$，再从 $p$ 前往 $j$；而 $p+1,\ldots,a_i$ 从 $p$ 均只需一元。因此

做法

子任务 1 可以建立所有可达边并运行 Floyd-Warshall，复杂度 $O(n^3)$。

子任务 2 按 $i$ 从大到小计算 $dp_i$，每次在线性扫描区间 $[i+1,a_i]$ 找到 $a_p$ 最大的位置，复杂度 $O(n^2)$。

满分算法用线段树或稀疏表回答区间最大值位置，把每次查找降为 $O(\log n)$ 或 $O(1)$，再使用上述递推。

正确性证明

从 $i$ 到 $i+1,\ldots,a_i$ 的距离均为一。对更右侧的终点，选择当前一步后可达最远的站 $p$ 不劣于其他第一步；其后续最短路已由 $dp_p$ 统计。$dp_p$ 中到 $p+1,\ldots,a_i$ 的距离都为一，递推式减去这 $a_i-p$ 项，剩余正好对应终点 $a_i+1,\ldots,n$。因此递推准确计算 $dp_i$，累加所有 $dp_i$ 即为答案。

复杂度

满分算法时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。