题目描述

信息学院的同学小明毕业之后打算创业开餐馆.现在共有 n 个地点可供选择。

小明打算从中选择合适的位置开设一些餐馆。

这 n 个地点排列在同一条直线上。

我们用一个整数序列 m1,m2,…,mn 来表示他们的相对位置。

由于地段关系,开餐馆的利润会有所不同。我们用 pi 表示在 mi 处开餐馆的利润。

为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于 k。

请你帮助小明选择一个总利润最大的方案。

输入格式
输入第一行是整数 T，表明有 T 组测试数据。紧接着有T组连续的测试。每组测试数据有 3 行。

第1行:地点总数 n, 距离限制 k；

第2行: n 个整数，表示 n 个地点的位置 m1,m2,…,mn(按升序排列)；

第3行: n 个整数，表示 n 个地点的餐馆利润 p1,p2,…,pn。

输出格式
输出共 T 行，每行输出一组测试数据可能的最大利润。

数据范围
1≤T≤1000,
n<100,
0<k<1000,
0<mi<106,
0<pi<1000

样例

输入样例：
2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30
输出样例：
40
30

(线性DP，最长上升子序列和)

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int t, n, m, a[1005], b[1005], f[1005];

int main()
{
    cin >> t;
    while(t--)
    {
        memset(f, 0, sizeof(f));//这里一定要清零，否则还会保留上一组数据
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            cin >> b[i];    
        int maxn = INT_MIN;//比大小初始值
        f[1] = b[1];
        for (int i = 2; i <= n; i++)
        {
            f[i] = b[i];
            for (int j = i - 1; j >= 0; j--) 
                if (a[i] - a[j] > m) f[i] = max(f[i], f[j] +b[i]);//这里是一大坑点，记住>m!
        }
        for (int i = 1; i <= n; i++)
            maxn = max(maxn, f[i]);//打擂比较，求最大值
        cout << maxn << endl;
    }
    return 0;
}