先把所有正段全部取上，再用二叉堆+双向链表的反悔贪心，以最小代价合并相邻正段或删掉正段，把段数压到不超过 M。
OJ: roj
题目 ID: 3057
难度:提高+/省选-
标签:贪心反悔贪心二叉堆链表python
创建: 2026-10-01 12:43
更新: 2026-10-07 13:50
形式化题目
给定长度为
即在"段数不超过
样例
正解
思路
第一步：把序列压成符号交替的段。 值为
其中
第二步：分三种平凡情形。
或 （没有正段）：一段都取不了，答案是 。 ：段数限制不起作用，全部正段都取，答案是 。
第三步：
- 删掉一个正段
：代价 ； - 越过一个负段
，把它和它两侧的正段并成一段：代价 （并进来时多损失的和）。
关键在于两种操作互相冲突：一个正段被删掉后，它两侧的负段也就不必再越过；一个负段被越过并与两侧正段合并后，这两个正段已经合成一段，不存在"删掉其中一半"的说法。把
则每种合法操作对应链上的一个点，冲突恰好是"相邻"：问题化为在链上选恰好
样例
| 元素 | 压缩后的段 | 链上的点 | 含义 |
|---|---|---|---|
| 删掉它代价 |
|||
| 越过它代价 |
|||
| 删掉它代价 |
|||
| 越过它代价 |
|||
| 删掉它代价 |
第四步：链上取
坑点：左右哨兵的指针必须指向自己（prv[0] = 0、nxt[s+1] = s+1），否则反悔到端点时会读到越界下标；堆里还要用 dead 标记做懒删除，跳过已被邻居吞并的历史记录。
经过
代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 13:02
# update_at: 2026-10-01 13:02
import heapq
import sys
from itertools import groupby
INF = 1 << 60 # 链表两端哨兵的权值：大到永远不会被选中，从而禁止“反悔到边界外”
def same_sign_runs(a: list[int]) -> list[tuple[bool, int]]:
"""把序列压成 (是否为正段, 该段数值和) 的交替列表，0 直接丢弃。"""
return [(sign, sum(run)) for sign, run in groupby((x for x in a if x), key=lambda x: x > 0)]
def min_merge_cost(path: list[int], t: int) -> int:
"""在路径上选 t 个两两不相邻的点，最小化权值和（堆 + 双向链表反悔）。
path 交替排列“删掉一个正段”的代价与“并掉一个负段”的代价：一次操作占用一个点，
相邻点互斥；取完 i 后把左右邻接进 i 并把权值改成 w[l]+w[r]-w[i]，
再选它一次就等于反悔、改选两侧。
"""
s = len(path)
w = [INF, *path, INF] # 下标 0 与 s+1 为哨兵
prv = [0, *range(s), s] # prv[0] 指回自己，反悔到左端时不会越界
nxt = [*range(1, s + 2), s + 1] # nxt[s+1] 同理指向自己
dead = bytearray(s + 2)
cost = 0
heap = [(w[i], i) for i in range(1, s + 1)]
heapq.heapify(heap)
for _ in range(t):
value, i = heapq.heappop(heap)
while dead[i]: # 已被左右邻居吞并的历史记录
value, i = heapq.heappop(heap)
cost += value
left, right = prv[i], nxt[i] # 相邻点与 i 互斥，只能合到一起再反悔
dead[left] = dead[right] = 1
w[i] = w[left] + w[right] - value
prv[i], nxt[i] = prv[left], nxt[right]
nxt[prv[left]] = prv[nxt[right]] = i
heapq.heappush(heap, (w[i], i))
return cost
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
a = [next(data) for _ in range(n)]
runs = same_sign_runs(a)
positive = [i for i, (sign, _) in enumerate(runs) if sign]
if m == 0 or not positive: # 一段都取不了，或根本没有正段
print(0)
return
total = sum(value for sign, value in runs if sign) # 取走所有正段
if len(positive) <= m:
print(total)
return
lo, hi = positive[0], positive[-1] # 首尾的负段并进来只会白亏，先剪掉
# 正段记"删掉它的代价"，负段记"并过它的代价"，于是问题变成路径上取 T 个互不相邻的点
path = [value if sign else -value for sign, value in runs[lo:hi + 1]]
print(total - min_merge_cost(path, len(positive) - m))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 17:03
* update_at: 2026-10-06 17:03
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXS = 2 * MAXN + 5; // 链上点数最多 2K-1，K 为压缩后的正段数
typedef long long ll;
ll n, m;
ll a[MAXN];
ll seg[MAXN]; // 压缩后的段和：正段为正，负段为负，0 已被丢弃
ll w[MAXS]; // 链上点权，下标 1..s，0 与 s+1 是 +INF 哨兵
ll prv[MAXS]; // 双向链表前驱
ll nxt[MAXS]; // 双向链表后继
char dead[MAXS]; // 懒删除标记，只有 0/1，用 char 控制内存
const ll INF = 1000000000000000LL; // 1e15：远大于任何合法代价之和，且相加不会溢出
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > heap;
// 在链上选恰好 t 个两两不相邻的点，返回最小点权和（堆 + 双向链表反悔贪心）。
// 每步取当前最小点 i，再让 i 原地变成左右邻居的"后悔药"：
// 删掉左右邻居，令 w[i] = w[left] + w[right] - w[i] 放回堆，
// 于是再选一次 i 的净代价变成 w[left] + w[right]，等价于撤销本次并改选左右两点。
ll min_nonadjacent_sum(int s, ll t) {
w[0] = INF;
w[s + 1] = INF;
prv[0] = 0; // 左哨兵指向自己，反悔到左边界时不会读到越界下标
nxt[s + 1] = s + 1; // 右哨兵同理
for (int i = 1; i <= s; i++) {
prv[i] = i - 1;
nxt[i] = i + 1;
}
nxt[0] = 1;
prv[s + 1] = s;
for (int i = 0; i <= s + 1; i++) {
dead[i] = 0;
}
while (!heap.empty()) {
heap.pop();
}
for (int i = 1; i <= s; i++) {
heap.push(make_pair(w[i], i));
}
ll cost = 0;
for (ll step = 1; step <= t; step++) {
pair<ll, int> cur = heap.top();
heap.pop();
ll value = cur.first;
int i = cur.second;
while (dead[i]) { // 已被左右邻居吞并的历史记录
cur = heap.top();
heap.pop();
value = cur.first;
i = cur.second;
}
cost += value;
int left = prv[i];
int right = nxt[i];
dead[left] = 1;
dead[right] = 1;
w[i] = w[left] + w[right] - value;
prv[i] = prv[left];
nxt[i] = nxt[right];
nxt[prv[left]] = i;
prv[nxt[right]] = i;
heap.push(make_pair(w[i], i));
}
return cost;
}
void solve() {
// 1. 压缩：跳过 0，把同号连续元素合并成符号交替的段
int cnt = 0;
int i = 1;
while (i <= n) {
if (a[i] == 0) {
i++;
continue;
}
int positive = (a[i] > 0) ? 1 : 0;
ll sum = 0;
while (i <= n) {
if (a[i] == 0) { // 0 不影响和，直接跳过，不打断同号段
i++;
continue;
}
if (((a[i] > 0) ? 1 : 0) != positive) {
break;
}
sum += a[i];
i++;
}
cnt++;
seg[cnt] = sum;
}
// 2. 统计正段个数、正段总和，以及首尾正段的下标
ll total = 0;
int pos_cnt = 0;
int first_pos = -1;
int last_pos = -1;
for (int j = 1; j <= cnt; j++) {
if (seg[j] > 0) {
total += seg[j];
pos_cnt++;
if (first_pos == -1) {
first_pos = j;
}
last_pos = j;
}
}
// 3. 平凡情形：一段都取不了，或段数不超过 M，全部正段都取
if (m == 0 || pos_cnt == 0) {
cout << 0 << "\n";
return;
}
if (pos_cnt <= m) {
cout << total << "\n";
return;
}
// 4. 建链：从第一个正段到最后一个正段，正段记删除代价，负段记并过代价。
// 需要在全部正段里做 t = pos_cnt - m 次操作，对应链上取 t 个不相邻的点。
int s = 0;
for (int j = first_pos; j <= last_pos; j++) {
s++;
if (seg[j] > 0) {
w[s] = seg[j];
} else {
w[s] = -seg[j];
}
}
ll t = pos_cnt - m;
cout << total - min_nonadjacent_sum(s, t) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
}
solve();
return 0;
}复杂度
- 时间复杂度：
。压缩与建链各扫一遍 ；堆的初始化为 ，每次取点、懒删除、放回都是 ，共 次。 时约 次堆操作，实测每个测例最慢 s，远低于 ms。 - 空间复杂度：
：段数组、链的点权、 prv/nxt指针表各；实测峰值约 MB，低于 MB 限制。
总结
- 全取正段是"免费"的贪心上界
，剩下的问题只有"让正段数减少 个需要付多少代价"。 - 每次"删一个正段"或"越过一个负段"是链上相邻的两个点，冲突结构是链而不是任意图，于是可以用堆 + 双向链表 + 反悔（
）在 内求出恰好 个不相邻点的最小权和。 - 两个易错点：
或全负时要输出 ；首尾的负段不会出现在链上，不能给它们留反悔位置，两端用 哨兵封住。