【贪心】[PA2012]Tanie linie

· · 题解

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

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

题意

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

分析

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

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

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