首页 > 试题广场 >

RAG系统最大收益

[编程题]RAG系统最大收益
  • 热度指数:41 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
我们在搭建一个基于 RAG(Retrieval-Augmented Generation,检索增强生成)的问答系统。系统每天会接收用户问题,并基于“知识库”检索相关材料后再生成答案。为了保证检索质量,知识库需要定期“更新”(例如重抽取文档、重算向量、重建索引等),但更新会消耗计算资源。另一方面,只有当知识库处于“有效”状态时,基于它进行的查询才有实际收益;知识库过期后继续查询几乎没有价值(可以视为收益 0)。

因此,在接下来的 n 个连续自然日(周期)内,我们需要规划每天是否进行“更新”、是否“查询”,以最大化净利润(总查询收益 − 总更新成本)。

规则说明

  • 初始状态:第 0 天开始时,知识库“过期”。
  • 更新生效:若在第 i 天执行更新,则从第 i 天起连续 d 天“有效”,覆盖区间 [i, i+d-1]。有效当日可以马上用于查询。
  • 每天允许的操作(每天最多选一个):
    • 更新并查询:当日支付 update_cost[i],同时获得当日查询收益 query_reward[i](因为更新后立即有效)。
    • 仅查询:若当日处于有效期,则获得 query_reward[i];若过期,则收益为 0。
    • 什么也不做:无成本、无收益(若当日处于有效期,仍会消耗有效期一天)。
  • 目标:在 n 天内,使“总查询收益 − 总更新成本”最大。

直观理解:更新能“刷新”后续 d 天的检索质量(可带来查询收益),但更新要花钱;不更新也能查,但只有在还没过期的有效日才有收益。


输入描述:
  • 第 1 行:n d
  • 第 2 行:update_cost(长度为 n,空格分隔)
  • 第 3 行:query_reward(长度为 n,空格分隔)


输出描述:
  • 一行一个整数:最大净利润
示例1

输入

4 2
3 2 4 2
5 0 5 0

输出

5

说明

  • 0天:更新查询,收益5−成本3=+2(有效覆盖第0、1天
  • 第1天:更新并查询,收益0−成本2=−2(有效置覆盖1、2天)
  • 2天:仅查询+5(仍在有效期
  • 3天:不操作+0
 2−2+5=5

备注:
  • 1 ≤ n ≤ 1e5
  • 1 ≤ d ≤ n
  • 1 ≤ update_cost[i] ≤ 1e4
  • 0 ≤ query_reward[i] ≤ 1e4

这道题你会答吗?花几分钟告诉大家答案吧!