【POJ Challenge】生日礼物
题目大意：给定一个长度为$n$的序列，允许选择不超过$m$个连续的部分，求元素之和的最大值。
数据范围：$1\le n, m\le 10^5$。
题解：
显然的一步转化，就是把连续的、同符号的元素求和变成一个。
这样就变成了一串正负号交替的序列。
现在把所有正数都加一起，如果满足条件就直接输出。
不满足的话，我们发现：
我们可以选取一个负数，这样可以合并左右两个正数。
我们也可以删掉一个正数。
以上两个操作，都会使我们的选取的个数$-\ -$。
至于到底应该怎么选呢？
就弄一个堆，每次拿出来代价最小的操作就好。
代码：
#include <bits/stdc++.h>#define N 100010 using namespace std;int a[N], b[N], nxt[N], pre[N];bool vis[N];char *p1, *p2, buf[100000];#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == '-')
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}struct Node {
int val, id;
friend bool operator < (const Node &a, const Node &b) {
return a.val > b.val;
}
};priority_queue<Node> q;int main() {
int n = rd(), m = rd();
for (int i = 1; i <= n; i ++ ) {
b[i] = rd();
}
int n1 = 1;
a[1] = b[1];
for (int i = 2; i <= n; i ++ ) {
if ((a[n1] <= 0 && b[i] <= 0) || (a[n1] >= 0 && b[i] >= 0)) a[n1] += b[i];
else a[ ++ n1] = b[i];
}
if (a[n1] <= 0) {
n1 -- ;
}
if (a[1] <= 0) {
for (int i = 1; i < n1; i ++ ) {
a[i] = a[i + 1];
}
n1 -- ;
}
n = n1;
int ans = 0, sum = 0;
for (int i = 1; i <= n; i ++ ) {
if (a[i] > 0) {
sum ++ ;
ans += a[i];
}
Node mdl;
mdl.val = abs(a[i]);
mdl.id = i;
q.push(mdl);
nxt[i] = i + 1;
pre[i] = i - 1;
a[i] = abs(a[i]);
}
// cout << ans << endl ;
// cout << sum << endl ;
nxt[n] = pre[1] = 0;
if (sum <= m) {
cout << ans << endl ;
return 0;
}
m = sum - m;
for (int i = 1; i <= m; i ++ ) {
Node mdl = q.top();
q.pop();
while (vis[mdl.id] && !q.empty()) {
mdl = q.top();
q.pop();
}
// cout << mdl.val << endl ;
if (vis[mdl.id])
break;
ans -= mdl.val;
if (q.empty())
break;
int tmp = mdl.id;
if (!pre[tmp]) {
vis[tmp] = true;
vis[nxt[tmp]] = true;
pre[nxt[nxt[tmp]]] = 0;
}
else if(!nxt[tmp]) {
vis[tmp] = true;
vis[pre[tmp]] = true;
nxt[pre[pre[tmp]]] = 0;
}
else {
vis[nxt[tmp]] = true;
vis[pre[tmp]] = true;
mdl.val = a[tmp] = a[nxt[tmp]] + a[pre[tmp]] - a[tmp];
if (nxt[nxt[tmp]])
pre[nxt[nxt[tmp]]] = tmp;
if (pre[pre[tmp]])
nxt[pre[pre[tmp]]] = tmp;
pre[tmp] = pre[pre[tmp]];
nxt[tmp] = nxt[nxt[tmp]];
q.push(mdl);
}
}
cout << ans << endl ;
return 0;
}
小结：这玩意儿好像叫模拟费用流吧，不会不会有空学/cy
