题目描述
北大信息学院的同学小明毕业之后打算创业开餐馆。现在共有 nnn 个地点可供选择，小明打算从中选择合适的位置开设一些餐馆。这 nnn 个地点排列在同一条直线上。我们用一个整数序列 m1,m2,…,mnm_1, m_2, \dots , m_nm1,m2,…,mn 来表示他们的相对位置。由于地段关系，开餐馆的利润会有所不同。我们用 pip_ipi 表示在 mim_imi 处开餐馆的利润。为了避免自己的餐馆的内部竞争，餐馆之间的距离必须大于 kkk。请你帮助小明选择一个总利润最大的方案。
输入
输入包含若干组测试数据。
第一行是整数 T (1≤T≤1000)(1 \le T \le 1000)(1≤T≤1000)，表明有 T组测试数据。
紧接着有 T 组连续的测试。每组测试数据有 333 行。
第 1 行: 地点总数 n (n<100)(n \lt 100)(n<100)，距离限制 k (0<k<1000)(0 \lt k \lt 1000)(0<k<1000)。
第 2 行: n个地点的位置 m1,m2,…,mnm_1, m_2, \dots, m_nm1,m2,…,mn (0<mi<1000000(0 \lt m_i \lt 1000000(0<mi<1000000 且为整数，升序排列)))。
第 3 行: n个地点的餐馆利润 p1,p2,…,pnp_1, p_2, \dots, p_np1,p2,…,pn (0<pi<1000(0 \lt p_i \lt 1000(0<pi<1000 且为整数)))。
输出
对于每组测试数据可能的最大利润。
输入输出样例
样例输入 #1
2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30样例输出 #1
40
30
//感觉还是背包问题,和背包差不多但又不是背包;
//整体思路如下,当我们考虑要不要建的时候,首先判断,能不能建;
//f数组表示的是第i位置的餐馆能获得的最大利益,所以每次都要在i位置和前i个位置进行比较,然后获取最大值;
//如果符合条件,然后进入规划,i位置的餐馆,如果我不在这个位置建,那我就是i-1的价值,如果我要建,那就是在j位置1建一个价值pi的餐馆
//然后两者比较
#include<bits/stdc++.h>
using namespace std;
const int N=10000;
int t,n,k,m[N],p[N],f[N];
int main()
{
cin>>t;
while(t--)
{
memset(f,0,sizeof f);
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=1;i<=n;i++)
for(int j=1;j<i;j++)
if(m[i]-m[j]>k) f[i]=max(f[i-1],f[j]+p[i]);
cout<<f[n]<<endl;
}
return 0;
}