保龄球

GitHub跳转原题关系图返回列表

把「k 个宽 w 的球」看成数轴上 k 个长度 w 的区间,按最后一个球的右端点设计 DP,重叠项用单调队列取区间最大值,做到 O(nk)。

OJ: roj

题目 ID: 1787

难度:提高+/省选-

标签:动态规划单调队列区间覆盖python

创建: 2026-10-08 02:44

更新: 2026-10-08 02:44

形式化题目

有一排 nn 个球瓶,第 ii 个球瓶的分值为 aia_i(可为负)。另有 kk 个保龄球,每个球占据连续 ww 个位置。

一次投球等价于在数轴上选一个长度恰为 ww 的区间 [L,L+w−1][L, L+w-1]:把该区间与 [1,n][1, n] 相交部分中仍立着的球瓶全部击倒,并得到它们分值之和;已经倒下的球瓶再被盖住不再计分(球可以经过空位)。击倒的球瓶永远留下空位,而位置 0,−1,…0, -1, \dots 与 n+1,n+2,…n+1, n+2, \dots 也是空位——所以区间允许部分伸出序列左右两端(例如 L⩽0L \leqslant 0 时只打中 1…L+w−11 \dots L+w-1)。

于是一个区间覆盖其左端到右端之间的位置,而击倒的球瓶集合恰好是 kk 个长度 ww 的区间之并(再与 [1,n][1,n] 相交)。求 kk 次投球后能得到的最大总分;一个球瓶最多计一次分。

多组数据:第一行 t⩽10t \leqslant 10,接着每组给出 n,k,wn, k, w 与 nn 个分值(每行一个)。数据范围 1⩽n⩽100001 \leqslant n \leqslant 10000,1⩽k⩽5001 \leqslant k \leqslant 500,1⩽w⩽1001 \leqslant w \leqslant 100,−10000⩽ai⩽10000-10000 \leqslant a_i \leqslant 10000。

提示

关于数据来源。 本题素材里的标程与测试数据都是本仓库用 data.py 自造生成的,题面按网络流传的「一本通 1787」重建,与官方原题可能存在偏差。10 个测试点分层覆盖了最小规模、题面样例、全负下界、w=1w=1 顶格、随机中小规模、全正铺满,以及 t=10t=10 的顶格最坏结构。

正解

思路

为什么贪心会错。 最顺手的想法是每次投出"当前 ww 连和最大的区间"再把那些球瓶清空,重复 kk 次。这个贪心在负数球瓶出现时就崩了。看题面第二个例子 2,8,−5,3,5,8,4,8,−62, 8, -5, 3, 5, 8, 4, 8, -6(k=3,w=3k=3, w=3,答案是 3838):最优解是 (2+8)+(3+5+8)+(4+8)(2+8) + (3+5+8) + (4+8)。第一个球故意伸到左边界之外,只打中 2,82, 8,从而跳过 −5-5;第三个球故意和第二个球重叠一格,用第二个球已经打出的空位避开 −6-6。这两步都依赖"当前最大 ww 连和"之外的信息:一个区间可以只覆盖 11 个到 ww 个新球瓶,取决于它的左右两端有多少已经是空位。贪心看不到这个自由度。

把状态挂到"区间的右端点"上。 观察重叠的几何:设上一个球的区间是 [p−w+1,p][p-w+1, p],本球的区间是 [i−w+1,i][i-w+1, i],且 i−w+1⩽p⩽i−1i-w+1 \leqslant p \leqslant i-1(两个区间相交)。由于 i−w+1⩾p−w+1i-w+1 \geqslant p-w+1,本球压住的那一段 [i−w+1,p][i-w+1, p] 完整落在上一个球的区间里——那几个位置一定是空的。所以本球真正新增的只有 p+1…ip+1 \dots i,得分恰好是 Si−SpS_i - S_p(SS 为前缀和),无需关心 pp 之前发生过什么。

这说明:只要知道"上一个球的右端点 pp 在哪",就能 O(1)O(1) 算出本次投球的增量。于是状态就定义为最后一个球的右端点:

  • A[i]A[i]:用 jj 个球、且第 jj 个球的右端点恰为 ii 时的最大得分;
  • B[i]B[i]:用至多 jj 个球、且所有球的右端点都 ⩽i\leqslant i 时的最大得分(位置 ii 打不打都行)。

BB 从 AA 的前缀最大值得到:B[i]=max⁡(B[i−1],A[i])B[i] = \max(B[i-1], A[i]),故 BB 对下标单调不减。j=0j=0 时 A[i]A[i] 全部不可达,B[i]=0B[i] = 0。

处理越界。 把序列右侧补 w−1w-1 个分值为 00 的空位,令 pos=n+w−1\mathrm{pos} = n + w - 1,右端点 ii 就允许取到 pos\mathrm{pos},这正是"球悬在右边界外"的情形,而且因为补位分值为 00,前缀和在补位段保持不变。左边界外伸的情形不用补位:只要 i−w+1⩽0i-w+1 \leqslant 0,本球的窗口左端就越出序列,此时"上一球的右端点"直接钳到 00,即 B[max⁡(0,i−w)]B[\max(0, i-w)]。

两条转移。 第 jj 个球右端点在 ii,它的窗口是 [i−w+1,i][i-w+1, i]:

  1. 不重叠 / 越出左边界。 上一球的右端点 p⩽i−wp \leqslant i-w,本球覆盖的 [i−w+1,i][i-w+1, i] 全是新球瓶,增量 Si−Smax⁡(0,i−w)S_i - S_{\max(0,i-w)},前置状态取 B[max⁡(0,i−w)][j−1]B[\max(0,i-w)][j-1]。
  2. 重叠。 上一球的右端点 p∈[max⁡(0,i−w+1), i−1]p \in [\max(0, i-w+1),\, i-1],本球只新增 p+1…ip+1 \dots i,得增量 Si−SpS_i - S_p,前置状态是 A[p][j−1]A[p][j-1](右端点恰为 pp,不能是 BB)。这一项 Si+max⁡p(A[p][j−1]−Sp)S_i + \max_p\big(A[p][j-1] - S_p\big),内层是固定 j−1j-1、随 ii 右移的滑动窗口最大值,窗口长度 w−1w-1,用单调队列摊还 O(1)O(1) 取出。
A[i][j]=max⁡(B[max⁡(0,i−w)][j−1]+Si−Smax⁡(0,i−w)⏟不重叠, Si+max⁡p∈[max⁡(0,i−w+1), i−1](A[p][j−1]−Sp)⏟重叠)A[i][j] = \max\Big(\underbrace{B[\max(0,i-w)][j-1] + S_i - S_{\max(0,i-w)}}_{\text{不重叠}},\ \underbrace{S_i + \max_{p \in [\max(0,i-w+1),\, i-1]}\big(A[p][j-1] - S_p\big)}_{\text{重叠}}\Big)

为什么重叠项只能从 AA 转移。 如果允许从 B[p′]B[p'] 转移,等于说"上一个球的右端点可以随便 ⩽p′\leqslant p'",那本球压住的位置到底空不空就无从保证了——会把还立着的负分球瓶当成空位跳过去,答案偏大。反过来,如果从 A[p]A[p] 转移(右端点恰为 pp),窗口 [p−w+1,p][p-w+1,p] 必然覆盖 [i−w+1,p][i-w+1,p],空位性质是推导出来的,不用额外假设。这是本题唯一的坑。

答案。 B[pos][k]B[\mathrm{pos}][k]。BB 对球数也单调不减(多出来的球扔到界外即可),所以它就是"至多 kk 个球"的答案;因为总能一个球瓶都不打,答案 ⩾0\geqslant 0,全负数据下输出 00。

验证。 用 n⩽12n \leqslant 12 的完全搜索(枚举所有右端点组合取并集)对拍 3000 组随机数据,C++ 与 Python 两版全部一致;题面样例 39/3839 / 38 也均可复现。

代码

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-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()
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-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;
}

复杂度

  • 时间:对每个球数 j∈[1,k]j \in [1, k]、每个右端点 i∈[1,n+w−1]i \in [1, n+w-1] 做一次摊还 O(1)O(1) 的转移,共 O(t⋅k⋅(n+w))O\big(t \cdot k \cdot (n + w)\big)。顶格 t=10,k=500,n=10000,w=100t=10, k=500, n=10000, w=100 约 5×1075 \times 10^7 次操作,C++ 跑完整个文件约 0.120.12 s(峰值内存 8.38.3 MB),Python 同规模约 8.48.4 s。
  • 空间:前缀和、AA、BB、单调队列各 O(n+w)O(n + w),配滚动数组后与 kk 无关。注意到 A[p][j−1]−SpA[p][j-1] - S_p 与 jj 无关地复用,实现里每层重算一次即可,不需要 O(nk)O(nk) 的表。

总结

本题的关键在于把"球击倒球瓶"的游戏动作翻译成数轴上的区间覆盖,再把"同一个球瓶只计一次分"翻译成"后一个球与前一球重叠的部分不算分"。有了这个几何视角,"每次只新增 11 到 ww 个球瓶"这件事就有了确切含义:新增段 = 本窗口减去上一窗口,长度由两球右端点的距离决定。

由此得到的状态设计比朴素 DP 多记一个量——最后一个球的右端点,换来了重叠转移的精确性。很多错误解法(包括本题素材的早期版本)只用"前 ii 个位置、jj 个球的最优值"做状态,会把没打空的负分球瓶当空位跳过,在随机数据上系统性偏大。写完 DP 后必须用 n⩽12n \leqslant 12 的暴力对拍确认这一点。

最后,把重叠项写成 Si+max⁡p(A[p][j−1]−Sp)S_i + \max_p(A[p][j-1] - S_p) 之后,内层前缀最大值的窗口长度恒为 w−1w-1,单调队列顺理成章地把 O(nkw)O(nkw) 降到 O(nk)O(nk)。这道题因此串起了"区间覆盖建模 → 记录端点 → 滑动窗口最大值优化"三步,是单调队列优化 DP 里几何感最强的一类练习。