懒得修格式了。
之前咕的文章…… 看心情更了,高考完当然是要先玩啦!
感谢 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 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code