AcWing 1025. 开餐馆(线性简单dp)
原题链接
简单
作者:
逸误
,
2024-03-05 08:57:59
,
所有人可见
,
阅读 42
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
int T,n,k;
int dp[N];//最后一个用到的餐馆,值:最大利润
int m[N],p[N];
int main()
{
cin>>T;
while(T--)
{
memset(dp,0,sizeof dp);
cin>>n>>k;
for(int i=1;i<=n;i++)
scanf("%d",&m[i]);
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
dp[1]=p[1];
for(int i=1;i<=n;i++)
{
dp[i]=p[i];//只选这个作为第一个也有p[i]!
for(int j=1;j<i;j++)
{
if(m[i]-m[j]>k)
dp[i]=max(dp[i],dp[j]+p[i]);
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,dp[i]);
cout<<res<<endl;
}
return 0;
}