开餐馆

题目描述

直线上有 $n$ 个可选地点，位置 $m_1 < m_2 < \dots < m_n$ （升序给出），在 $m_i$ 开店的利润为 $p_i$ ；要选一些地点开餐馆，使任意两家餐馆的距离大于 $k$ ，求最大总利润。输入第一行为测试组数 $T$ ，每组数据 3 行： $n$ 与 $k$ 、 $n$ 个升序位置、 $n$ 个利润，输出每组数据的最大利润。范围： $1 \leqslant T \leqslant 1000$ ， $n < 100$ ， $0 < k < 1000$ ， $0 < m_i < 10^6$ ， $0 < p_i < 1000$ ，均为整数。下面样例中两组数据分别输出 40 和 30：

text

思路

定义 $dp[i]$ 为以第 $i$ 个地点作为最后一家店时的最大利润；由于位置升序，「任意两家距离大于 $k$ 」等价于每对相邻被选的店距离大于 $k$ ，所以转移为 $dp[i] = p_i + \max\bigl(0,\ \max_{j<i,\ m_i-m_j>k} dp[j]\bigr)$ 。答案取 $\max_i dp[i]$ ，因为最后一家店不一定开在最右边。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:41
# update_at: 2026-09-30 03:41

import sys

NONE = 0  # 位置升序，i 前面可能一家都接不上；利润恒正，0 就是「没有前驱」的哨兵


def max_profit(spots: list[int], profits: list[int], k: int) -> int:
    """求「任选若干地点且相邻两店距离严格大于 k」的最大利润和。

    dp[i] 表示以第 i 个地点收尾时的最大利润：要么前面一家都不开（前驱利润记 NONE），
    要么接在某个满足 spots[i] - spots[j] > k 的地点 j 后面。
    每个 i 只依赖前面这一段的 dp 最优值，所以单独扫一遍前缀即可。
    """
    dp = profits[:]  # 初值 = 只开 i 这一家
    for i in range(len(spots)):
        # spots 升序，能接的前驱必定是前缀；取该前缀上 dp 的最大值
        dp[i] += max((dp[j] for j in range(i) if spots[i] - spots[j] > k), default=NONE)
    return max(dp)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)  # 测试数据组数
    out: list[str] = []

    for _ in range(T):
        n, k = next(data), next(data)          # 地点数、距离限制
        spots = [next(data) for _ in range(n)]  # 升序的位置序列 m
        profits = [next(data) for _ in range(n)]
        out.append(str(max_profit(spots, profits, k)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:10
 * update_at: 2026-10-05 08:10
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 105;

ll n, k;              // 地点数、最小间距限制
ll m[MAXN];           // m[i]: 第 i 个地点的位置（升序）
ll p[MAXN];           // p[i]: 在第 i 个地点开店的利润
ll dp[MAXN];          // dp[i]: 以第 i 个地点作为最后一家店时的最大利润

// 处理一组数据：读入并做线性 DP
void solve() {
    scanf("%lld %lld", &n, &k);
    for (ll i = 1; i <= n; i++) scanf("%lld", &m[i]);
    for (ll i = 1; i <= n; i++) scanf("%lld", &p[i]);

    ll ans = 0;
    // 位置升序，能接在 i 前面的店 j 一定满足 m[i] - m[j] > k
    // 利润都为正，没有合法前驱时 dp[i] 就是 p[i] 自己
    for (ll i = 1; i <= n; i++) {
        dp[i] = p[i];
        for (ll j = 1; j < i; j++)
            if (m[i] - m[j] > k && dp[j] + p[i] > dp[i])
                dp[i] = dp[j] + p[i];
        if (dp[i] > ans) ans = dp[i]; // 答案取所有收尾位置的最大值
    }
    printf("%lld\n", ans);
}

int main() {
    ll T;
    scanf("%lld", &T);
    for (ll t = 1; t <= T; t++) solve();
    return 0;
}

目录

题目描述

思路

参考代码