题解

思路

设最终贡献最大的三个景点位置为 $i<j<k$。把路线端点缩到 $i,k$ 不会丢掉这三个景点，只会缩短距离，因此最优值等价于

做法

小规模可直接枚举 $i,j,k$，复杂度 $O(n^3)$。

中等规模固定 $i,k$，随着 $k$ 向右移动维护区间 $(i,k)$ 内最大的 $b_j$，即可在 $O(n^2)$ 内求解。

满分做法把式子拆成

预处理 prefix[j-1] 为 $j$ 左侧最大的 $b_i+i$，suffix[j+1] 为 $j$ 右侧最大的 $b_k-k$。枚举中间位置 $j$，三项相加取最大值。

正确性证明

任一合法路线中三个最高景点的最左、最右位置记为 $i,k$。把路线改为 $[i,k]$ 后三者仍在路线内，且扣除的距离不增，所以存在最优路线以所选三点的两端为边界。于是枚举有序三元组的目标式与原问题完全等价。

对固定 $j$，左侧项与右侧项互不影响，分别取 $i<j$ 中最大的 $b_i+i$ 和 $k>j$ 中最大的 $b_k-k$ 就得到所有以 $j$ 为中点的三元组最优值。枚举全部 $j$ 后必然覆盖全局最优三元组，因此算法正确。

复杂度分析

前后缀各扫描一次，枚举中点一次。每组时间复杂度 $O(n)$，空间复杂度 $O(n)$。