自动搬运

查看原文

来自洛谷，原作者为

	bai_tang 只要有信念，就一定能成功！

搬运于2025-08-24 22:24:20，当前版本为作者最后更新于2022-10-10 15:07:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

只要有信念，就一定能成功！

做法更简单，只用一个堆，思路来源。

题意

给一个长为 $n$ 的序列，求选择至多 $k$ 个不交连续子段的最大子段和，$n,k\le 10^6$。

分析

此题数据范围如此之大，DP 正常情况下无法设计出合适的状态来解决此问题，考虑贪心。

考虑当 $k$ 极大的时候，答案一定是所有正数的和，考虑从反向考虑，也就是从“很多个段”变成“一个段”。

容易发现，极大的连续非负段和极大连续负段总是同时选或者同时不选比较优秀，考虑把它们合并，问题变成一个正负交替数列，一开始你选了所有正的数，接下来你有两种操作：合并两个段（也就是加入两个段之间的那个为负的元素），删除一个段，而这可以直接用堆实现，代码。