容易想到 dp：设 \(dp_{i,p}\) 表示前 \(i\) 天，强制第 \(i\) 天 dry，并且一共消除了 \(p\) 个区间的答案。
转移时可以考虑枚举前面的决策 \(j\)，此时有转移方程：
\[dp_{i,p}=\max(dp_{j,p-w})+1 \]其中 \(w\) 为满足 \(l\in(j,i],r\in[i,n]\) 的区间 \([l,r]\) 个数。
显然可以考虑套路动态维护随着 \(i\) 的移动，对于每个决策 \(j\) 的 \(w\) 值：考虑每次 \(i\to i+1\)，我们都会干掉所有 \(r=i\) 的区间，加入所有 \(l=i+1\) 的区间。而转移时我们从 \(i\) 向前找，每找到一个区间左端点，\(w\) 就自增。而又由于 \(k\le 10\)，故我们最多只需要找到 \(10\) 段 \(w\) 不同的决策。不妨开 \(k+1\) 个线段树分别维护对于每个 \(p\) 值，区间 dp 最大值，转移时线段树辅助查询转移即可。可以用 multiset 维护合法区间左端点。
总时间复杂度 \(O(nk\log n)\)。
动态维护状态对决策贡献。
标签：Hard,Drying,Doremy,决策,区间,维护,转移,dp From： https://www.cnblogs.com/ydtz/p/17797208.html