把「k 个宽 w 的球」看成数轴上 k 个长度 w 的区间,按最后一个球的右端点设计 DP,重叠项用单调队列取区间最大值,做到 O(nk)。
OJ: roj
题目 ID: 1787
难度:提高+/省选-
标签:动态规划单调队列区间覆盖python
创建: 2026-10-08 02:44
更新: 2026-10-08 02:44
形式化题目
有一排
一次投球等价于在数轴上选一个长度恰为
于是一个区间覆盖其左端到右端之间的位置,而击倒的球瓶集合恰好是
多组数据:第一行
关于数据来源。 本题素材里的标程与测试数据都是本仓库用 data.py 自造生成的,题面按网络流传的「一本通 1787」重建,与官方原题可能存在偏差。10 个测试点分层覆盖了最小规模、题面样例、全负下界、
正解
思路
为什么贪心会错。 最顺手的想法是每次投出"当前
把状态挂到"区间的右端点"上。 观察重叠的几何:设上一个球的区间是
这说明:只要知道"上一个球的右端点
:用 个球、且第 个球的右端点恰为 时的最大得分; :用至多 个球、且所有球的右端点都 时的最大得分(位置 打不打都行)。
处理越界。 把序列右侧补
两条转移。 第
- 不重叠 / 越出左边界。 上一球的右端点
,本球覆盖的 全是新球瓶,增量 ,前置状态取 。 - 重叠。 上一球的右端点
,本球只新增 ,得增量 ,前置状态是 (右端点恰为 ,不能是 )。这一项 ,内层是固定 、随 右移的滑动窗口最大值,窗口长度 ,用单调队列摊还 取出。
为什么重叠项只能从
答案。
验证。 用
代码
#!/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-08 02:44
# update_at: 2026-10-08 02:44
import sys
NEG = -(10 ** 30) # 不可达状态哨兵:远小于任何真实得分(|总分| ≤ 10^8)
def best_score(vals: list[int], k: int, w: int) -> int:
"""一组数据(分值表 vals、k 个球、每个球宽 w)能拿到的最大总分。
pos = n + w - 1:把右边界外补 w-1 个分值为 0 的空位,球就允许悬在右边界外;
左边界外同理(由 q 被钳到 0 的那个分支表达)。pre 是前缀和。
"""
n = len(vals)
pos = n + w - 1
pre = [0] * (pos + 1)
total = 0
for i in range(1, n + 1):
total += vals[i - 1]
pre[i] = total
for i in range(n + 1, pos + 1):
pre[i] = total # 空位不得分:前缀和保持不变
prev_a = [NEG] * (pos + 1) # 0 个球时「最后一个球右端点恰为 i」不可达
prev_b = [0] * (pos + 1) # 0 个球时「右端点都不超过 i」得分为 0
dq = [0] * (pos + 1) # 单调队列(存下标),维护 key 在窗口内的最大值
for _ in range(k):
# 重叠转移只用到 prev_a[p] - pre[p]:把「上一球右端点 p」对分值的净贡献先算好
key = [prev_a[p] - pre[p] for p in range(pos + 1)]
cur_a = [NEG] * (pos + 1)
cur_b = [0] * (pos + 1)
head = tail = 0
running = 0 # cur_b[i],B 对 i 单调不减
for i in range(1, pos + 1):
p = i - 1 # 候选的「上一球右端点」逐个入队
while tail > head and key[dq[tail - 1]] <= key[p]:
tail -= 1 # 队尾比新来的小,永远不会再当选
dq[tail] = p
tail += 1
lo = i - w + 1 # 重叠要求上一球窗口盖到本窗口左端 i-w+1
while head < tail and dq[head] < lo:
head += 1
# 情况一:与上一球重叠,本球只新增 p+1..i
best = NEG if head >= tail else pre[i] + key[dq[head]]
# 情况二:与上一球不重叠(q = i-w ≥ 0),或球从左边界外伸进来(钳到 q = 0,
# 此时 1..i 整段都是新球瓶;prev_b[0] - pre[0] = 0 恰好就是「前面没有球」)
q = i - w if i > w else 0
cand = pre[i] + prev_b[q] - pre[q]
if cand > best:
best = cand
cur_a[i] = best
if best > running:
running = best # 位置 i 可打可不打
cur_b[i] = running
prev_a, prev_b = cur_a, cur_b
# B 对球数单调不减,所以 B[pos][k] 就是「至多 k 个球」的答案;全负数据下它是 0
return prev_b[pos]
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
tests = next(data)
for _ in range(tests):
n, k, w = next(data), next(data), next(data)
vals = [next(data) for _ in range(n)]
out.append(str(best_score(vals, k, w)))
print('\n'.join(out))
if __name__ == "__main__":
solve()/**
* 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-08 02:44
* update_at: 2026-10-08 02:44
*/
// main.cpp:ROJ 1787《保龄球》,按「球」扫描的 DP + 单调队列优化。
//
// 题意:n 个球瓶(分值可负),k 个球,每个球恰好占据连续 w 个位置(可以伸到
// 球瓶 1 左边或球瓶 n 右边的空位上),把它盖住的球瓶全部击倒并得分;一个球瓶
// 只计一次分。求最大总分。
//
// 建模:问题等价于在数轴上选 k 个长度 w 的区间,覆盖集合与 [1,n] 相交处的分值
// 之和最大。把球按右端点从小到大排序,第 j 个球相对「前 j-1 个球的最大右端点 p」
// 只有两种情况:与上一球不重叠(p ≤ i-w,整段都是新的),或与上一球重叠
// (p ∈ [i-w+1, i-1],只有 p+1..i 是新增的)。于是只需记录「最后一个球的右端点
// 恰好是 i」这一状态,重叠项的区间最大值用单调队列摊还 O(1) 取出。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10005; // 球瓶数上限
const int MAXW = 105; // 球宽上限
const int MAXPOS = MAXN + MAXW; // 右边界外补 w-1 个空位后的长度上限
int n, k, w; // 球瓶数、球数、球宽
int pos; // 补空位后的位置总数 pos = n + w - 1
ll pre[MAXPOS]; // 前缀和,补的空位分值为 0(前缀和保持不变)
ll prevA[MAXPOS], curA[MAXPOS]; // A[i]:最后一个球右端点恰为 i 时的最大得分
ll prevB[MAXPOS], curB[MAXPOS]; // B[i]:所有球右端点都 ≤ i 时的最大得分(至多 j 个球)
int dq[MAXPOS]; // 单调队列(存下标),维护 A[p] - pre[p] 的区间最大值
const ll NEG = -(1LL << 60); // 不可达状态哨兵,远小于任何真实得分(|答案| ≤ 10^8)
// 一次投球:从位置 i 的状态推下一层,A/B 各滚动一层
void run_case() {
scanf("%d %d %d", &n, &k, &w);
pos = n + w - 1; // 球可以越出右边界,右端点在 n+1..n+w-1 也算合法落点
pre[0] = 0;
for (int i = 1; i <= n; i++) {
ll v;
scanf("%lld", &v);
pre[i] = pre[i - 1] + v;
}
for (int i = n + 1; i <= pos; i++) pre[i] = pre[n]; // 空位不得分
for (int i = 0; i <= pos; i++) { // 0 个球:A 不可达,B 恒为 0
prevA[i] = NEG;
prevB[i] = 0;
}
for (int j = 1; j <= k; j++) {
int head = 0, tail = 0; // 队列区间 dq[head..tail-1]
curA[0] = NEG;
curB[0] = 0;
for (int i = 1; i <= pos; i++) {
// 第 j 个球的窗口是 [i-w+1, i],把候选的「上一球右端点」p 全部入队
int p = i - 1;
ll key = prevA[p] - pre[p]; // 重叠转移里只随 p 变化的部分
while (tail > head && prevA[dq[tail - 1]] - pre[dq[tail - 1]] <= key) tail--;
dq[tail++] = p;
int lo = i - w + 1; // 重叠要求上一球窗口覆盖到本窗口左端,即 p ≥ i-w+1
if (lo < 0) lo = 0;
while (head < tail && dq[head] < lo) head++;
ll best = NEG;
if (head < tail) { // 情况一:与上一球重叠,只新增 p+1..i 这段
int bp = dq[head];
best = pre[i] + prevA[bp] - pre[bp];
}
int q = i - w; // 情况二:与上一球不重叠(或球从左边界外伸进来),整段都新增
if (q < 0) q = 0;
ll disjoint = prevB[q] + pre[i] - pre[q];
if (disjoint > best) best = disjoint;
curA[i] = best;
curB[i] = (curB[i - 1] > best) ? curB[i - 1] : best; // 至多 j 个球,位置 i 可打可不打
}
for (int i = 0; i <= pos; i++) { // 滚动到下一层
prevA[i] = curA[i];
prevB[i] = curB[i];
}
}
// B 对 j 单调不减,故 B[pos][k] 就是「至多 k 个球」的答案;全负数据下它是 0
printf("%lld\n", prevB[pos]);
}
int main() {
int t;
if (scanf("%d", &t) != 1) return 0;
while (t--) run_case(); // 多组数据,所有数组都在 run_case 里重置
return 0;
}复杂度
- 时间:对每个球数
、每个右端点 做一次摊还 的转移,共 。顶格 约 次操作,C++ 跑完整个文件约 s(峰值内存 MB),Python 同规模约 s。 - 空间:前缀和、
、 、单调队列各 ,配滚动数组后与 无关。注意到 与 无关地复用,实现里每层重算一次即可,不需要 的表。
总结
本题的关键在于把"球击倒球瓶"的游戏动作翻译成数轴上的区间覆盖,再把"同一个球瓶只计一次分"翻译成"后一个球与前一球重叠的部分不算分"。有了这个几何视角,"每次只新增
由此得到的状态设计比朴素 DP 多记一个量——最后一个球的右端点,换来了重叠转移的精确性。很多错误解法(包括本题素材的早期版本)只用"前
最后,把重叠项写成