AcWing 1025. 开餐馆
原题链接
简单
作者:
摆神
,
2024-04-27 10:59:55
,
所有人可见
,
阅读 1
开餐馆
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int t,n,k;
int score[N];
int a[N];//位置
int f[N];//F[i] 第i个地点前所有利润(属性:最高利润)
int main(void)
{
cin >> t;
while(t --){
cin >> n >> k;
int res = 0;
//输入数据
for(int i = 1;i <= n;i ++){
int x;
cin >> x;
a[i] = x;
}
for(int i = 1;i <= n;i ++){
int y;
cin >> y;
score[i] = y;
}
for(int i = 1;i <= n;i ++){
f[i] = score[i];//初始化
//不能在下一个for循环内,在下一个for循环中每进行一次重置它一次,我们要求在里面不能重置
for(int j = 0;j < i;j ++)
{
//满足下一个存放的位置
if(a[i] - a[j] > k) f[i] = max(f[i] , f[j] + score[i]);
//找出每个地点前最大的利润
res = max(res , f[i]);
}
}
cout << res << endl;
}
return 0;
}