Author: lllyouo
Date: 20250225
tag:
link:

问题描述

分析

略

参考代码

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

const int N = 110;
int n, k, a[N], b[N];
// 考虑前在第 i 个位置开餐馆能获得的最大利润
int f[N];

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];

        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i++) {
            int t = 0;
            // 枚举上一个获得最大利润的餐馆的位置
            for (int j = i - 1; j >= 1; j--) {
                if (a[i] - a[j] > k) {
                    t = max(t, f[j]);
                }
            }
            // 加上当前位置的利润
            f[i] = t + b[i];
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
        cout << ans << endl;
    }
    return 0;
}