AcWing 1025. 开餐馆
原题链接
简单
作者:
不幸到吃土
,
2025-01-09 21:19:17
,
所有人可见
,
阅读 2
//思路类似"最长上升子序列"
//状态表示:f[i]表示从第一个餐馆起,以a[i]餐馆为结尾的最大价值
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int d[N]; //存储各餐馆的位置
int w[N]; //存储各餐馆的利润
int f[N];
int main(){
int T;
cin >> T;
while(T--){
int n,k;
cin >> n >> k;
for(int i=1;i<=n;i++)
cin >> d[i];
for(int i=1;i<=n;i++)
cin >> w[i];
//开始DP
for(int i=1;i<=n;i++){
f[i] = w[i]; //各餐馆的初始价值为本身
for(int j=1;j<i;j++){
if(d[i] - d[j] > k)
f[i] = max(f[i],f[j] + w[i]);
}
}
int ans = 0;
for(int i=1;i<=n;i++){
ans = max(ans,f[i]);
}
cout << ans << endl;
}
return 0;
}