题解：CF1616D Keep the Average High

中缀自动机 · 2024-12-09 21:08:17 · 题解

题面

先将所有的 a_i 都减掉 x，要求变为了所有长度为 2 的区间和 \ge0。

注意到，我们只需验证每个长度为 2 或 3 的区间。

那么自然可以考虑 dp，记 f_{i,0/1,0/1} 表示当前考虑了前 i 个数，是否选择 a_{i−1} 和 a_i。转移枚举 a_{i+1} 是否选择，并验证是否满足要求即可。

时间复杂度 O(n)。

实际上这里可以直接从左到右贪心选取。