思路与算法

两端各补w个0表示场外空白。pre为前缀和。记录用至多t球、只在前i格击倒的最优值best[t][i]，以及最右击倒位置恰为i的end[t][i]。最后一球若不重叠，候选best[t-1][i-w]+pre[i]-pre[i-w]；若与上一个最右区间重叠，候选end[t-1][j]+pre[i]-pre[j]，i-w<j<i。用单调队列维护end-prevPre的滑窗最大值，再令best[t][i]=max(best[t][i-1],end[t][i])。两层滚动。

正确性说明

把最后一球按最右端i分类。此前覆盖不超过i-w时，与它不重叠，新增完整w格；否则此前最右击倒端点j落在重叠区，之前结束于j的最后一段至少长w，已覆盖本球左端到j，所以只新增j+1..i。两类穷尽全部覆盖并集，每个递推都能由真实球区间实现。队列只删除过期j或被更晚且不劣候选支配的j，不丢最优。补0允许边缘部分击中，滚动t得到最优。

复杂度

O(k(n+w))时间、O(n+w)空间，含补零、前缀和与每层队列/滚动数组初始化。

易错点

不能只选互不重叠的长度w区间，后来的球可以借此前空白避开负分。不能直接把原数组中的负值都删掉；同一球跨度以内的未倒负瓶仍必须计分。不使用球也可保留0分。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, k, w;
        cin >> n >> k >> w;
        int N = n + 2 * w;
        vector<long long> pre(N + 1);
        for (int i = 1; i <= N; i++) {
            int v = 0;
            if (i > w && i <= w + n)
                cin >> v;
            pre[i] = pre[i - 1] + v;
        }
        const long long NEG = -(1LL << 60);
        vector<long long> old(N + 1), oldEnd(N + 1, NEG), cur(N + 1), curEnd(N + 1);
        for (int t = 1; t <= k; t++) {
            deque<int> q;
            fill(curEnd.begin(), curEnd.end(), NEG);
            cur[0] = 0;
            for (int i = 1; i <= N; i++) {
                int j = i - 1;
                while (!q.empty() && oldEnd[q.back()] - pre[q.back()] <= oldEnd[j] - pre[j])
                    q.pop_back();
                q.push_back(j);
                while (!q.empty() && q.front() < i - w + 1)
                    q.pop_front();
                long long best = NEG;
                if (i >= w)
                    best = old[i - w] + pre[i] - pre[i - w];
                if (!q.empty())
                    best = max(best, oldEnd[q.front()] + pre[i] - pre[q.front()]);
                curEnd[i] = best;
                cur[i] = max(cur[i - 1], best);
            }
            old.swap(cur);
            oldEnd.swap(curEnd);
        }
        cout << old[N] << "\n";
    }
}