题解 | RAG系统最大收益

还是搜索

维护四个状态：

到了第几天，目前剩余有效期还有几天，累积收益多少元，累积成本多少元

以及小剪枝

要预处理一个前缀和

方便用来看如果后续收益全拿满也不够最好状态的收益与成本的差，那么就没必要往后继续搜了

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

int n,d;
int cost[100005];
int rwd[100005];
int ans=-1;
int sum[100005];
void dfs(int pos,int lft,int rev,int cst)//到了第i天，目前剩余有效期有几天，收益多少元，成本多少元 
{
	if(pos==n+1)
	{
		ans=max(rev-cst,ans);
		return;
	}
	if(sum[n]-sum[pos-1]+rev-cst<ans)return;
	if(lft)
	{
		dfs(pos+1,lft-1,rev+rwd[pos],cst);
		dfs(pos+1,d-1,rev+rwd[pos],cst+cost[pos]);
	}
	else
	{
		dfs(pos+1,d-1,rev+rwd[pos],cst+cost[pos]);
		dfs(pos+1,lft,rev,cst);
	}
}	

int main()
{
	cin>>n>>d;
	for(int i=1;i<=n;i++)
		cin>>cost[i];
	for(int i=1;i<=n;i++)
		{
			cin>>rwd[i];
			sum[i]=sum[i-1]+rwd[i];
		}
	dfs(1,0,0,0);
	cout<<ans;
}