懒得修格式了。
之前咕的文章…… 看心情更了，高考完当然是要先玩啦！
感谢 icy 的指正，之前有个地方 i，j 搞反了，已更正。
顺便安利：hopeless cactus V 开发现场直播间
题目
一个区间 (元素是一个 pair，priority 和 value) 分成可以若干段，每段的贡献是段中 priority 最大的对应的 value(可能小于 0)，求最好的分组方案对应的最大的贡献值。
要求复杂度 $O(n)$。
解
传统方法
首先，有一个很显然的 dp 状态是令 $f_{i}$ 表示分组分隔位置为 i 时前 i 个数构成的贡献的最大值。
但这是 $O(n^2)$的，据说好像可以做到 $O(n log_{2}n)$ ，还没想出来咋优化。
???
受到这篇文章中提到的第二个题的启发，换个 DP 状态，令 $f_{i}$ 表示 $i$ 被选中 (选中即为在最终分组之后成为各自的组的 priority 最大值) 时前 $i$ 个数的最大贡献值。
那么转移是这样的：$$
f_{i}=(\underset{i,j 满足某条件}{max}f_{j})+value_{i}
$$
探究一下某条件是什么。
可以发现当且仅当满足：
$$\exists k\in [j,i-1],\forall p\in[i,k],priority_{p}\leq priority_{i} 且 \forall q\in[k+1,j],priority_{q}\leq priority_{j}$$
可以转移 (k 就是分组分割点)。
这个条件显然又可以化简为：
$$
\forall k\in[j+1,i-1],priority_{k}\leq max(priority_{i},priority_{j})
$$
max 不好直接处理，分类讨论:
若 max 取在 i，则当前任务是” 找出 i 前面第一个 priority 值比 i 的 priority 值大的位置，对这个位置到 i 的区间的 f 值求 max”，因为在这个位置之后，所有位置满足转移条件，而之前的所有位置不满足条件。这部分用单调栈维护，每次入栈时维护一个当前栈顶和即将入栈的元素之间的 f 最大值，出栈时和当前手中的最大值合并。复杂度 $O(n)$。
若 max 取在 j，在维护前一种情况的单调栈时，对栈中元素多记一个从栈底到当前元素的 f 最大值，压栈时和栈顶取 max，更新时拿栈顶元素上维护的 f 最大值更新。复杂度不变。
0 条评论