1025. 开餐馆(最长上升子序列模型)
作者:
闪回
,
2024-04-08 17:42:02
,
所有人可见
,
阅读 2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 110;
int n,k;
int m[N],p[N];
int f[N];
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>k;
for(int i = 1;i<=n;i++)cin>>m[i];
for(int i = 1;i<=n;i++)cin>>p[i];
f[1] = p[1];
for(int i = 2;i<=n;i++)
{
f[i] = p[i];
for(int j = 1;j<i;j++)
{
if(m[i] - m[j] > k)
{
f[i] = max(f[i],f[j] + p[i]);
}
}
}
int res = 0;
for(int i = 1;i<=n;i++)res = max(res,f[i]);
cout<<res<<endl;
}
}