题解 | #RAG系统最大收益#

题目链接

RAG系统最大收益

题目描述

在基于 RAG（检索增强生成）的问答系统中，知识库需要定期更新以保持有效性。

在接下来的 $n$ 个连续自然日内，给定每日的更新成本 $update\_cost[i]$ 和查询收益 $query\_reward[i]$ 。
初始状态下，知识库是“过期”的。
若在第 $i$ 天执行更新，则知识库从第 $i$ 天起连续 $d$ 天处于“有效”状态（覆盖区间 $[i, i+d-1]$ ），期间可以获得查询收益。
每天可以从以下三种操作中选择一个：
1. 更新并查询：支付 $update\_cost[i]$ ，若当日有效则获得 $query\_reward[i]$ 。
2. 仅查询：若当日处于有效期内，获得 $query\_reward[i]$ ；否则收益为 0。
3. 什么也不做：无成本无收益。
目标：计算 $n$ 天内能获得的最大净利润（总收益 $-$ 总成本）。

输入描述：

第一行： $n, d$ 。
第二行： $n$ 个整数，代表 $update\_cost[i]$ 。
第三行： $n$ 个整数，代表 $query\_reward[i]$ 。

输出描述：

一个整数，代表最大净利润。

解题思路

这是一个带有时间窗口约束的动态规划问题，可以通过单调队列进行优化。

状态定义：设 $dp[i]$ 表示前 $i$ 天（即日期 $0, \dots, i-1$ ）能获得的最大净利润。
状态转移：对于第 $i$ 天（对应的索引为 $i-1$ ）：
- 如果第 $i-1$ 天不进行有效的查询（即不处于任何更新周期，或主动放弃），则 $dp[i] = dp[i-1]$ 。
- 如果第 $i-1$ 天处于某个更新周期内，假设该周期的起始更新日为 $j$ （ $i-d \le j < i$ ），则该周期从 $j$ 到 $i-1$ 的总收益为 $\sum_{k=j}^{i-1} query\_reward[k] - update\_cost[j]$ 。
- 转移方程： $dp[i] = \max(dp[i-1], \max_{i-d \le j < i} \{ dp[j] - update\_cost[j] + \sum_{k=j}^{i-1} query\_reward[k] \})$ 。
优化：引入前缀和 $P[i] = \sum_{k=0}^{i-1} query\_reward[k]$ 。则 $\sum_{k=j}^{i-1} query\_reward[k] = P[i] - P[j]$ 。转移方程变为： $dp[i] = \max(dp[i-1], P[i] + \max_{i-d \le j < i} \{ dp[j] - update\_cost[j] - P[j] \})$ 。令 $V[j] = dp[j] - update\_cost[j] - P[j]$ ，该项仅与 $j$ 相关。我们可以使用单调队列维护滑动窗口 $[i-d, i-1]$ 内 $V[j]$ 的最大值。
复杂度：
- 每个元素入队和出队各一次，时间复杂度为 $\mathcal{O}(n)$ 。
- 空间复杂度为 $\mathcal{O}(n)$ ，用于存储数组和单调队列。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

typedef long long LL;

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

    vector<LL> P(n + 1, 0);
    for (int i = 0; i < n; ++i) P[i + 1] = P[i] + reward[i];

    vector<LL> dp(n + 1, 0);
    vector<LL> V(n);
    deque<int> dq;

    for (int i = 1; i <= n; ++i) {
        int j = i - 1;
        V[j] = dp[j] - cost[j] - P[j];
        
        while (!dq.empty() && V[j] >= V[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(j);
        
        if (dq.front() < i - d) {
            dq.pop_front();
        }
        
        dp[i] = max(dp[i - 1], P[i] + V[dq.front()]);
    }

    cout << dp[n] << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        long[] cost = new long[n];
        long[] reward = new long[n];
        for (int i = 0; i < n; i++) cost[i] = sc.nextLong();
        for (int i = 0; i < n; i++) reward[i] = sc.nextLong();

        long[] P = new long[n + 1];
        for (int i = 0; i < n; i++) P[i + 1] = P[i] + reward[i];

        long[] dp = new long[n + 1];
        long[] V = new long[n];
        Deque<Integer> dq = new ArrayDeque<>();

        for (int i = 1; i <= n; i++) {
            int j = i - 1;
            V[j] = dp[j] - cost[j] - P[j];
            
            while (!dq.isEmpty() && V[j] >= V[dq.peekLast()]) {
                dq.pollLast();
            }
            dq.offerLast(j);
            
            if (dq.peekFirst() < i - d) {
                dq.pollFirst();
            }
            
            dp[i] = Math.max(dp[i - 1], P[i] + V[dq.peekFirst()]);
        }

        System.out.println(dp[n]);
    }
}

from collections import deque

def solve():
    n, d = map(int, input().split())
    costs = list(map(int, input().split()))
    rewards = list(map(int, input().split()))

    p_sum = [0] * (n + 1)
    for i in range(n):
        p_sum[i + 1] = p_sum[i] + rewards[i]

    dp = [0] * (n + 1)
    v_vals = [0] * n
    dq = deque()

    for i in range(1, n + 1):
        j = i - 1
        v_vals[j] = dp[j] - costs[j] - p_sum[j]
        
        while dq and v_vals[j] >= v_vals[dq[-1]]:
            dq.pop()
        dq.append(j)
        
        if dq[0] < i - d:
            dq.popleft()
            
        # dp[i] 可以是不查询，或者在这个窗口内更新
        dp[i] = max(dp[i - 1], p_sum[i] + v_vals[dq[0]])

    print(dp[n])

if __name__ == "__main__":
    solve()

算法及复杂度

算法：动态规划 $+$ 单调队列优化。
时间复杂度： $\mathcal{O}(n)$ 。通过前缀和与单调队列将转移时间从 $\mathcal{O}(d)$ 优化至 $\mathcal{O}(1)$ ，总复杂度与天数 $n$ 成线性关系。
空间复杂度： $\mathcal{O}(n)$ 。需要存储成本、收益、前缀和、状态及单调队列。