思路

价值单调递增，把最长上升子序列的距离改成价值的和即可， 在判断距离是否大于K的时候选择更新一下即可。

代码

#include <bits/stdc++.h>
#define intceil(a, b) ((a + b - 1) / b)
#define all(_) _.begin(), _.end()
using namespace std;

template <typename T>
inline void read(T &f) {
  f = 0; T fu = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
  while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
  f *= fu;
}

typedef long long LL;
typedef pair<int, int> PII;

const int N = 101, M = 100010, INF = 0x3f3f3f3f;
int f[N], m[N], p[N];
// f[i]表示前i个地点方案集合的最大价值, 地点距离按距离排序，
// 可以把最长子序列的板子修改一下，把之前的距离1修改成本题的价值
// 然后根据距离是否大于K来更新价值，转移到最后的一定是最大的价值
void solve() {
  int n, k; read(n), read(k);
  memset(f, 0, sizeof f);
  for(int i = 1; i <= n; i++) read(m[i]); // 地点
  for(int i = 1; i <= n; i++) read(p[i]); // 价值

  for(int i = 1; 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]); // 满足题意就加上之前的价值
      else f[i] = max(f[i], f[j]); // 否则就转移过来
    }
  }

  printf("%d\n", f[n]);
}

int main() {
  int _; read(_);
  while(_--) solve();
}