6821

本来想写 wqs 二分来着，然后推不出 dp 方程，摆烂了。 题目描述 给定含 \(n\) 个数的序列，求至多 \(k\) 个不相交子段的和的最大值。 具体思路 由于选 \(k\) 堆连续的数，因此一堆连续的符号相同的数，只有可能是同时被选或者同时不被选。 因此我们先对原序列预处理一遍，将相同符号的 ......

这里只讲[加强版](https://www.luogu.com.cn/problem/CF280D)，这是严格弱化。 结论是贪心。每次取出最大和连续子段，目前答案加上这个子段和，然后再把这个子段取反（相反数T），然后求整个过程答案的最大值。 考虑费用流模型。对于 $i\le n$，$S\to i$ ......

[洛谷传送门](https://www.luogu.com.cn/problem/P6821 "洛谷传送门") 考虑恰好选 $k$ 个子段怎么做。 设恰好选 $i$ 个子段的和最大值为 $h_k$。可以得到 $h_{i + 1} - h_i \le h_i - h_{i - 1}$，因为 $h_i ......