题解：P14154 [ICPC 2022 Nanjing R] 索道

Priestess_SLG · 2025-10-06 18:53:16 · 题解

先考虑不带修怎么做。容易想到设 f_i 表示当前考虑了前 i 个位置，且第 i 个位置放了支撑塔，最少所花费的代价是多少。容易想到 O(n^2) 转移：枚举上一个设支撑塔的位置 j，转移为 f_i=(\min\limits_{j}f_j)+a_i，其中 j 需要满足 j+1\sim i-1 中不能存在一个必须设立支撑塔的位置，且 i-j\le k。容易想到用单调队列优化，时间复杂度为 O(n)。

然后考虑带修。注意到 kq\le 9\times 10^6，因此想到每次询问可能时间复杂度带一个 O(k)。容易发现任意一个长度为 k 的连续子段中都至少存在一个支撑塔，因此考虑对于每次修改，先提前再处理出 g_i 表示当前考虑了 i\sim n 的位置，且第 i 个位置放了支撑塔，最少所花费的代价是多少。暴力的处理出 [p-k,p+k] 区间内的 dp 值，然后直接拼接到 f 和 g 两个 dp 数组上，时间复杂度为 O(n+kq) 可以通过。