解题思路

题目给出连续 n 个周期，每个周期有：

• update_cost[i]：本周期执行“更新”的成本（正整数）
• query_reward[i]：本周期执行“查询”的收益（非负整数，只有知识库有效时才有）

知识库规则：

• 初始为过期（第 0 周期若想有收益必须更新）。

• 一旦在周期 i 更新，知识库从周期 i 起 连续有效 d 个周期（包含 i），即覆盖区间 [i, i+d-1]。

• 每个周期可选操作包含“只查询 / 只更新 / 先更新后查询 / 暂停”等，但由于：

  • 查询无成本且收益非负
  • 在本周期更新后立即有效 所以：
  • “只更新”一定不如“更新并查询”（多拿 query_reward[i]，无额外代价）
  • “暂停”一定不如“（有效时）查询”（多拿 query_reward[i]，无额外代价）

因此每个周期实际上只需考虑两类决策：

1. 不更新：若当前有效则获得 query_reward[i]，否则获得 0，有效期减少 1。
2. 更新：支付 update_cost[i]，并获得 query_reward[i]，有效期重置为 d（本周期已用掉 1，所以到下一周期剩 d-1）。

关键在于：收益只取决于“最近一次更新时间”。

• 若最近一次更新在 j，则周期 t 有收益当且仅当 t-j < d。

这类问题可用 动态规划（DP）+ 单调队列维护滑动窗口最大值 来做到 O(n)：

定义：

• R[x]：query_reward 的前缀和，R[x]=sum_{0..x-1} reward。
• f[k]：最后一次更新发生在周期 k 时，到周期 k 为止的最大净利润（已包含周期 k 的“更新并查询”收益，即 reward[k]-cost[k]，以及之前有效期内的查询收益）。

从某个上一次更新 i 转移到在 k 更新，中间能拿到的查询收益只覆盖到 i+d-1：

• 若 k <= i+d：中间收益是 sum_{t=i+1..k-1} reward[t] = R[k]-R[i+1]
• 若 k > i+d：中间收益是 sum_{t=i+1..i+d-1} reward[t] = R[i+d]-R[i+1]

把转移拆成两类并维护最大值：

• 类1（i >= k-d，即 k 仍在 i 的有效期内）：

  • 贡献：f[i] - R[i+1] + R[k]
  • 需要对区间 [k-d, k-1] 做滑动最大值，用单调队列维护 f[i]-R[i+1]

• 类2（i < k-d，即 k 已超过 i 的有效期）：

  • 贡献：f[i] + R[i+d] - R[i+1]
  • 与 k 无关，只需维护前缀最大值即可

并且允许“此前从未更新”，其历史利润为 0（可以先空等，没收益没成本）：

最终：

• f[k] = (reward[k]-cost[k]) + max( 0, R[k]+M1, M2 )

  • M1：窗口 [k-d, k-1] 上 f[i]-R[i+1] 的最大值（单调队列）
  • M2：所有 i <= k-d-1 上 f[i]+R[i+d]-R[i+1] 的最大值（前缀最大）

答案还要考虑最后一次更新在 i 后，剩余有效期内还能继续查询到结束：

• 总利润候选：f[i] + (R[min(n, i+d)] - R[i+1])
• 取所有 i 的最大值与 0 的最大值。

复杂度分析

• 时间复杂度：O(n) 单调队列每个下标最多进出一次，整体线性。
• 空间复杂度：O(n)（保存 f 和前缀和），队列额外 O(d) 但不超过 O(n)。

代码实现

Python

import sys
from collections import deque

def solve(n, d, cost, reward):
    # 前缀和 R[x] = sum(reward[0..x-1])
    R = [0] * (n + 1)
    for i in range(n):
        R[i + 1] = R[i] + reward[i]

    NEG = -10**30
    f = [NEG] * n

    # 单调队列维护 val1[i] = f[i] - R[i+1] 的滑动最大值
    dq = deque()

    # M2：维护 val2[i] = f[i] + R[i+d] - R[i+1] 的前缀最大值（只对 i <= k-d-1）
    M2 = NEG

    for k in range(n):
        # 把 i = k-1 加入单调队列，供当前 k 使用
        if k - 1 >= 0:
            i = k - 1
            v1 = f[i] - R[i + 1]
            while dq and (f[dq[-1]] - R[dq[-1] + 1]) <= v1:
                dq.pop()
            dq.append(i)

        # 弹出窗口左端之外的下标：需要 i >= k-d
        left = k - d
        while dq and dq[0] < left:
            dq.popleft()

        # 更新 M2：当 k 增加时，会新增 i = k-d-1 进入“已过期集合”
        j = k - d - 1
        if j >= 0:
            v2 = f[j] + (R[j + d] - R[j + 1])
            if v2 > M2:
                M2 = v2

        best_prev = 0

        # 类1：仍在有效期内的转移
        if dq:
            M1 = f[dq[0]] - R[dq[0] + 1]
            cand = R[k] + M1
            if cand > best_prev:
                best_prev = cand

        # 类2：已过期的转移
        if M2 > best_prev:
            best_prev = M2

        # 本周期更新并查询：收益 reward[k]，成本 cost[k]
        f[k] = (reward[k] - cost[k]) + best_prev

    # 计算最终答案：最后一次更新在 i 后还能查询到 min(n-1, i+d-1)
    ans = 0
    for i in range(n):
        end = i + d
        if end > n:
            end = n
        tail_gain = R[end] - R[i + 1]
        total = f[i] + tail_gain
        if total > ans:
            ans = total

    return ans

def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    d = int(data[1])

    cost = list(map(int, data[2:2 + n]))
    reward = list(map(int, data[2 + n:2 + 2 * n]))

    print(solve(n, d, cost, reward))

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayDeque;

public class Main {

    // 核心功能：计算最大净利润
    private static long solve(int n, int d, int[] cost, int[] reward) {
        long[] R = new long[n + 1];
        for (int i = 0; i < n; i++) {
            R[i + 1] = R[i] + reward[i];
        }

        final long NEG = -(long)1e18;
        long[] f = new long[n];
        for (int i = 0; i < n; i++) f[i] = NEG;

        // 单调队列维护 val1[i] = f[i] - R[i+1] 的窗口最大值
        ArrayDeque<Integer> dq = new ArrayDeque<>();

        // M2：维护 val2[i] = f[i] + (R[i+d] - R[i+1]) 的前缀最大值
        long M2 = NEG;

        for (int k = 0; k < n; k++) {
            // 将 i = k-1 放入队列
            if (k - 1 >= 0) {
                int i = k - 1;
                long v1 = f[i] - R[i + 1];
                while (!dq.isEmpty()) {
                    int last = dq.peekLast();
                    long lastV1 = f[last] - R[last + 1];
                    if (lastV1 <= v1) dq.pollLast();
                    else break;
                }
                dq.addLast(i);
            }

            // 移除不在窗口 [k-d, k-1] 的下标
            int left = k - d;
            while (!dq.isEmpty() && dq.peekFirst() < left) {
                dq.pollFirst();
            }

            // 更新 M2：新增 j = k-d-1
            int j = k - d - 1;
            if (j >= 0) {
                long v2 = f[j] + (R[j + d] - R[j + 1]);
                if (v2 > M2) M2 = v2;
            }

            long bestPrev = 0;

            // 类1：窗口内转移
            if (!dq.isEmpty()) {
                int idx = dq.peekFirst();
                long M1 = f[idx] - R[idx + 1];
                long cand = R[k] + M1;
                if (cand > bestPrev) bestPrev = cand;
            }

            // 类2：过期集合转移
            if (M2 > bestPrev) bestPrev = M2;

            // 本周期更新并查询：reward[k] - cost[k]
            f[k] = (long)reward[k] - (long)cost[k] + bestPrev;
        }

        // 统计最终答案：最后一次更新后剩余有效期内的查询收益
        long ans = 0;
        for (int i = 0; i < n; i++) {
            int end = i + d;
            if (end > n) end = n;
            long tailGain = R[end] - R[i + 1];
            long total = f[i] + tailGain;
            if (total > ans) ans = total;
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        int[] cost = new int[n];
        int[] reward = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) cost[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) reward[i] = Integer.parseInt(st.nextToken());

        System.out.println(solve(n, d, cost, reward));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 核心功能：计算最大净利润
static long long solve(int n, int d, const vector<int>& cost, const vector<int>& reward) {
    vector<long long> R(n + 1, 0);
    for (int i = 0; i < n; i++) {
        R[i + 1] = R[i] + reward[i];
    }

    const long long NEG = -(long long)4e18;
    vector<long long> f(n, NEG);

    // 单调队列维护 val1[i] = f[i] - R[i+1] 的窗口最大值
    deque<int> dq;

    // M2：维护 val2[i] = f[i] + (R[i+d] - R[i+1]) 的前缀最大值
    long long M2 = NEG;

    for (int k = 0; k < n; k++) {
        // 将 i = k-1 放入队列
        if (k - 1 >= 0) {
            int i = k - 1;
            long long v1 = f[i] - R[i + 1];
            while (!dq.empty()) {
                int last = dq.back();
                long long lastV1 = f[last] - R[last + 1];
                if (lastV1 <= v1) dq.pop_back();
                else break;
            }
            dq.push_back(i);
        }

        // 移除不在窗口 [k-d, k-1] 的下标
        int left = k - d;
        while (!dq.empty() && dq.front() < left) dq.pop_front();

        // 更新 M2：新增 j = k-d-1
        int j = k - d - 1;
        if (j >= 0) {
            long long v2 = f[j] + (R[j + d] - R[j + 1]);
            M2 = max(M2, v2);
        }

        long long bestPrev = 0;

        // 类1：窗口内转移
        if (!dq.empty()) {
            int idx = dq.front();
            long long M1 = f[idx] - R[idx + 1];
            bestPrev = max(bestPrev, R[k] + M1);
        }

        // 类2：过期集合转移
        bestPrev = max(bestPrev, M2);

        // 本周期更新并查询：reward[k] - cost[k]
        f[k] = (long long)reward[k] - (long long)cost[k] + bestPrev;
    }

    // 统计最终答案：最后一次更新后剩余有效期内的查询收益
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int end = i + d;
        if (end > n) end = n;
        long long tailGain = R[end] - R[i + 1];
        ans = max(ans, f[i] + tailGain);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, d;
    cin >> n >> d;

    vector<int> cost(n), reward(n);
    for (int i = 0; i < n; i++) cin >> cost[i];
    for (int i = 0; i < n; i++) cin >> reward[i];

    cout << solve(n, d, cost, reward) << "\n";
    return 0;
}

题目内容

在基于 $RAG$ (检索增强生成) 技术的智能问答系统中，知识库的时效性直接影响查询服务的质量。系统每天(周期)可通过更新知识库维持其有效性，或基于当前知识库处理用户查询获取收益。由于更新知识库需要消耗计算资源(如文档嵌入、索引重建)，而查询收益仅在知识库有效的情况下才能获得，因此需要动态平衡“更新成本"与“查询收益”，制定最优运营策略。

给定 $n$ 个连续周期，第 $i$ 个周期 $i (0≤i ＜n)$ 有两个参数；

$update\_cost[i]$：第 $i$ 周期更新知识库的成本(正整数)。

$query\_reward[i]$：第 $i$ 周期使用当前知识库处理查询的收益(非负整数)，仅当知识库有效时可获得。

核心规则：

知识库有效期：每次更新后，知识库进入“有效状态”，有效期持续 $d$ 个 周期(含更新所在周期)。例如：若 $d=2$ ，第 $3$ 周期更新后，第 $3、4$ 周期有效，第 $5$ 周期过期。

操作选择：每个周期可执行如下操作之一:

仅查询：若知识库有效，获得 $query\_reward[i]$ 收益，无成本；若知识库过期，收益为 $0$ 。

仅更新：支付 $update\_cost[i]$ 成本，重置有效期(从当前周期开始持续 $d$ 个周期)，无直接收益。

先更新后查询：支付 $update\_cost[i]$ 成本，获得 $query\_reward[i]$ 收益(更新后立即有效)

暂停：无成本，无收益，知识库状态不变(如果当前周期知识库有效，暂停会消耗一个有效周期;过期则保持过期)。

初始状态：知识库初始为“过期”状态(第 $0$ 周期若要查询，必须先更新)。

目标：计算 $n$ 个连续周期内可获得的最大净利润(总收益 - 总更新成本)。

输入描述

第一行为连续周期数 $n$ 和持续周期 $d$ ，用空格隔开

第二行为 $update\_cost$ 数组，用空格隔开

第三行为 $query\_reward$ 数组，用空格隔开

输出描述

最大净利润，整数

样例1

输入

3 2
100 100 100
1 1 1

输出

0

样例2

输入

3 3
10 20 30
5 10 15

输出

20

说明

在 $3$ 个周期中，最优策略是：

周期 $0$ ：更新并查询(利润：$-5$ )

周期 $1$ ：查询 (利润：$+10$ )

周期 $2$ ：查询 (利润： $+15$ ) 最终累计最大净利润为 $20$ 。

提示

$1≤n≤10^5$ (至少 $1$ 个周期)

$1≤d≤n$ (折扣间隔 $d$ ，有效期持续 $d$ 个周期)

$1≤update\_cost[i]≤10^4$ (正整数，每个周期的更新成本至少为 $1$ )

$0≤query\_reward[i]≤ 10^4$ (非负整数，收益可零但不可为负)