思路：可以发现这序列是一段上升一段下降的锯齿形。先考虑拿到所有正数，此时如果段数大于m，考虑怎么最小代价减少段的数量，从 负数和最小的开始合并？而且要考虑负数和超过正数和的情形，注意特殊情况是这段和为0时，并不需要合并，直接跳过。减小个数的方案是，要么这段大于0，去掉这个及左右2边，并合并，这样可能会给后面的答案贡献更小的答案；要么这段小于0，就是将左右2边大于0的合并减少了1个区间。
代码：
#include <cstdio> #include <cstring> #include <set> #include <algorithm> using namespace std; typedef long long ll; template <class T> inline bool rd(T &ret) { char c; int sgn; if(c = getchar() , c == EOF) return false; while(c != ‘-‘ && (c < ‘0‘ || c > ‘9‘)) c = getchar(); sgn = (c == ‘-‘) ? -1 : 1; ret = (c == ‘-‘) ? 0 : (c - ‘0‘); while(c = getchar(), c >= ‘0‘ && c <= ‘9‘) ret = ret * 10 + (c - ‘0‘); ret *= sgn; return true; } const int N = 2000005; ll s[N]; set<pair<ll, int> > a; int n, m, now; int pr[N], ne[N]; void Erase(int x) { int l = pr[x], r = ne[x]; if (l) ne[l] = r; if (r) pr[r] = l; } int main() { rd(n), rd(m); ll tem = 0, ans = 0; int cnt = 0; for(int i = 1, x; i <= n; ++i) { rd(x); if((tem < 0 && x > 0) || (tem > 0 && x < 0)) { now += tem > 0; s[++cnt] = tem; a.insert(make_pair(abs(tem), cnt)); tem = 0; } tem += x; ans += x > 0 ? x : 0; } now += tem > 0; s[++cnt] = tem; a.insert(make_pair(abs(tem), cnt)); for( int i = 1; i <= cnt; ++i) pr[i] = i - 1, ne[i] = i + 1; ne[cnt] = s[0] = 0; while (now > m) { int x = (*a.begin()).second; a.erase(make_pair(abs(s[x]), x)); if (s[x] < 0 && (!pr[x] || !ne[x]) || !s[x]) continue; a.erase(make_pair(abs(s[pr[x]]), pr[x])),a.erase(make_pair(abs(s[ne[x]]), ne[x])); ans -= abs(s[x]); s[x] = s[x] + s[pr[x]] + s[ne[x]]; Erase(pr[x]), Erase(ne[x]); a.insert(make_pair(abs(s[x]), x)); --now; } printf("%I64d\n", ans); return 0; } /* 7 2 -2 11 -4 13 -5 6 -2 7 2 1 -10 2 -9 3 -8 4 6 1 1 -1 1 -1 1 -1 */
原文：http://www.cnblogs.com/Rojo/p/4851387.html
