Doremy's Drying Plan (Hard Version) - 洛谷
-
很好的一道 \(dp\) 题，无论是 \(dp\) 状态还是优化都很思维
-
我们设 \(dp_{i,j}\) 表示考虑了前 \(i\) 个城市，第 \(i\) 个城市干旱，删除了 \(j\) 天的最多干旱城市。转移时我们枚举上一个干旱城市的位置 \(k\)，为了防止一天的天气被重复删除，我们强制钦定在这天影响的区间 \([l,r]\) 中最左边的干旱城市位置删除天气。
-
考虑覆盖 \(i\) 的所有区间 \([l_i,r_i]\)
-
当 \(l_i \leq k\) 时，说明 \(i\) 是最左边的干旱天气
-
当 \(l_i > k\) 时，说明 \(i\) 不是最左边的干旱天气
-
-
记第一种情况的区间个数为 \(t\)，可以得到转移：
-
\[dp_{i,j}=\max dp_{k,j-t} +1 \]
-
最终复杂度 \(O(n^2k)\)，能想到这里已经很好了，但我们还要考虑继续优化
-
我们发现 \(j \leq K\)，因此我们可以对于 \(j\) 相同的 \(dp\) 优化取 \(\max\) 的过程，可以发现取到的 \(\max\) 一定是一段区间，因此我们考虑寻找一个数据结构可以做到：
-
在末尾插入一个数
-
查询区间 \([l,r]\) 的最大值
-
-
线段树也许可以，但复杂度 \(O(nk^2 \log n)\) 可能很不好过。但我们发现我们只需要在末尾插入一个数，因此我们尝试使用 \(st\) 表。
-
具体的，我们倒着维护 \(st\) 表，即 \(st_{i,j}\) 维护 \([j-2^i+1,j]\) 的 \(\max\)
-
最终复杂度 \(O(nk^2 + nk\log n)\)，可以通过