6821
题解 P6821 [PA2012] Tanie linie
本来想写 wqs 二分来着,然后推不出 dp 方程,摆烂了。 题目描述 给定含 \(n\) 个数的序列,求至多 \(k\) 个不相交子段的和的最大值。 具体思路 由于选 \(k\) 堆连续的数,因此一堆连续的符号相同的数,只有可能是同时被选或者同时不被选。 因此我们先对原序列预处理一遍,将相同符号的 ......
Luogu 6821 PA2012 Tanie linie
这里只讲[加强版](https://www.luogu.com.cn/problem/CF280D),这是严格弱化。 结论是贪心。每次取出最大和连续子段,目前答案加上这个子段和,然后再把这个子段取反(相反数T),然后求整个过程答案的最大值。 考虑费用流模型。对于 $i\le n$,$S\to i$ ......