思路与算法

定义dp[i]为前i头牛的最大收益，前缀和p[i]。若末尾选取j+1至i，则j位置不选（j=0表示从头选），候选收益为p[i]+dp[j-1]-p[j]，且i-K≤j<i；还可不选i得到dp[i-1]。用单调队列维护窗口内表达式dp[j-1]-p[j]的最大值，逐步推进。K读成非负数字文本并截到n，因为超过n的限制与n等价。

正确性说明

任何合法方案若最后选了i，末段连续选取区间唯一，其前一位置必须不选，故前缀最优与末段收益可相加。枚举末段长度1至K覆盖全部情况，不选i的分支也保留。队列删去过期j和数值不优于后来候选的旧j：后来j有效期更长且值更大，旧j永远不会成为最佳。因此队首恰为当前最优转移，归纳得dp最优。

复杂度

前缀和与两个数组初始化O(n)，每个j至多进出队列各一次，时间O(n+len(K))，空间O(n)，含前缀、dp和队列。n≤10^5、效率≤10^9，总收益≤10^14，用long long。

易错点

K=0时一头也不能选；K≥n时可选全部。队列保存候选j而非效率值，转移中必须用dp[j-1]，不是dp[j]。独立答案使用按连续已选长度转移的O(nK)DP，满规模K=n则以全部非负收益和独立核对。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string text;
    cin >> n >> text;
    int k = 0;
    for (char c : text)
        k = min(n, k * 10 + (c - '0'));
    vector<long long> p(n + 1), dp(n + 1);
    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        p[i] = p[i - 1] + x;
    }
    deque<int> q;
    q.push_back(0);
    auto value = [&](int j) {
        return (j ? dp[j - 1] : 0) - p[j];
    };
    for (int i = 1; i <= n; ++i) {
        while (!q.empty() && q.front() < i - k)
            q.pop_front();
        dp[i] = dp[i - 1];
        if (!q.empty())
            dp[i] = max(dp[i], p[i] + value(q.front()));
        while (!q.empty() && value(q.back()) <= value(i))
            q.pop_back();
        q.push_back(i);
    }
    cout << dp[n] << '\n';
}