P3592 [POI2015] MYJ

P3592 [POI2015] MYJ

要求总和最大，有两张思路：贪心和 dp。稍微想一下，发现贪心思考量太大，考虑 dp

观察 n 的数据范围，以及转移方式，可以想到区间 dp

发现转移跟区间最小值有关，设 \(f_{l,r,k}\) 为区间 \([l,r]\) 中最小值不小于 \(x\) 的答案。

转移枚举最小值的位置 \(p\)，\(f_{l,r,k}=\max(f_{l,p-1,k}+f_{p+1,r,k}+cost(l,r,p,i))\)

\(cost(l,r,p,i)\) 表示最小值在 \(p\) 处时的贡献，即 \(l\le a_i\le p\le b_i\le r\) 且 \(c_i\ge k\) 的数量。转移时预处理 \(buc_{l,r}\) 表示 \([l,r]\) 中的区间数量即可。

还有转移 \(f_{l,r,k}=f_{l,r,k+1}\)，容易理解。

现在的复杂度为 \(O(n^3\max(c_i))\)，无法通过。发现对于每个位置，我们都只会选择在 \(c_i\) 中出现过的，否则一定不优。所以离散化 \(c_i\)，复杂度降到 \(O(n^3m)\)，可以通过。

答案为 \(f_{1,n,1}\)。

考虑打印方案，只需要在转移时记录断点以及断点处的值，dfs 一遍即可。