AcWing 1025. 开餐馆
原题链接
简单
作者:
y总的小迷弟
,
2023-10-08 10:59:15
,
所有人可见
,
阅读 66
//写一手状态机awa;
//设f[i][0]表示选前i家商店,第i家选货不选的集合;
//属性:max;
//转移:见代码;
#include<bits/stdc++.h>
using namespace std;
int n, k;
int a[110], p[110];
int f[110][2];
int main()
{
int T;
cin >> T;
while(T--)
{
memset(f, 0, sizeof(f));
cin >> n >> k;
for(int i = 1;i <= n;i++)
cin >> a[i];
for(int i = 1;i <= n;i++)
cin >> p[i];
memset(f, -0x3f, sizeof(f));
f[0][0] = 0;
//合法和不合法状态初始化;
for(int i = 1;i <= n;i++)
{
f[i][0] = f[i - 1][0];
for(int j = i - 1;j >= 0;j--)
{
if(a[i] - a[j] <= k)
f[i][1] = max(f[i][1], f[j][0] + p[i]);
else
f[i][1] = max(f[i][1], max(f[j][1], f[j][0]) + p[i]);
}
}
int ans = 0;
for(int i = 1;i <= n;i++)
ans = max(ans, max(f[i][0], f[i][1]));
cout << ans << endl;
}
return 0;
}