CF 1826D

题目内容

给定一列数 $a_{1}, a_{2}, \dots, a_{n}$ ，定义函数 $f (l, r)$ 的值为 $a_{l}, a_{l + 1}, \dots, a_{r}$ 中值最大的三个数之和减去 $(r - l)$ 。求对于所有的 $l, r \in [1, n]$ 最大的 $f (l, r)$ 。

解法

提示一

子序列中三个最大值的位置是否存在某些隐含的性质？

提示二

提示一的答案：三个最大值的两个必然落在区间两端，即为 $b_{l}$ 与 $b_{r}$ 。

解答

提示三给出的性质是显然的。因为如果两个最大值不落在子序列两端，则两端的数对于答案的贡献是负的（白白增加了序列长度），不如去掉。固定了两个答案贡献的位置，不妨设第三个最大值的位置为 $i$ ，且 $l < i < r$ 。考虑对 $f$ 的表达式作简单变形得到 $f = a_{i} + (a_{l} + l) + (a_{r} - r)$ ，此时 $f$ 的三个部分都可以独立处理：处理出 $(a_{l} + l)$ 的前缀最大值与 $(a_{r} + r)$ 的后缀最大值，再枚举所有的 $a_{i}$ 即可得到答案。时间复杂度为 $Θ (n)$ 。

AC 代码

见提交记录。