04118: 开餐馆

dp, http://cs101.openjudge.cn/practice/04118

北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列 $m_{1}, m_{2}, . . . m_{n}$ 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用 $p_{i}$ 表示在 $m_{i}$ 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。

输入

标准的输入包含若干组测试数据。输入第一行是整数 $T (1 \leq T \leq 10^{3})$ ，表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行, 第1行：地点总数 $n (n < 100)$ , 距离限制 $k (0 < k < 10^{3})$ . 第2行：n 个地点的位置 $m_{1}, m_{2}, . . . m_{n}$ ( $0 < m_{i} < 10^{6}$ 且为整数，升序排列) 第3行：n 个地点的餐馆利润 $p_{1}, p_{2}, . . . p_{n}$ ( $0 < p_{i} < 10^{3}$ 且为整数)

输出

对于每组测试数据可能的最大利润

样例输入

样例输出

40
30

为每个地点计算出在其上开餐馆所能获得的最大利润，然后通过遍历和选择相隔至少为 ( k ) 的位置来确保利润最大化。使用一个 DP 数组 dp[i]，其中 dp[i] 表示到第 i 个位置为止的最大利润。

思路

初始化 dp[i] = prof[i]，即第 i 位置开餐馆的初始利润。
对于每一个地点 i ，遍历前面所有地点 j ，检查：
- 如果 loc[i] - loc[j] > k ，即位置差大于距离限制 k ，则可以选择在 j 和 i 两个位置开餐馆。
- 更新 dp[i] 为 dp[j] + prof[i] 的最大值。

105ms AC

python

def max_profit(n, k, loc, prof):
    dp = prof[:]  # Initialize dp with profits at each location

    for i in range(n):
        for j in range(i):
            if loc[i] - loc[j] > k:  # Check if the distance is greater than k
                dp[i] = max(dp[i], dp[j] + prof[i])

    return max(dp)

for _ in range(int(input())):
    n, k = map(int, input().strip().split())
    locations = list(map(int, input().strip().split()))
    profits = list(map(int, input().strip().split()))

    print(max_profit(n, k, locations, profits))

33ms AC。二分查找来优化这一过程。

python

from bisect import bisect_left

def max_profit(n, k, m, p):
    # dp[i] 表示前 i 个地点能获得的最大利润
    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        # 使用二分查找找到位置与 m[i-1] 至少差 k 的最大 j 值
        j = bisect_left(m, m[i-1] - k)  # 找到第一个小于 m[i-1] - k 的位置

        # 在 i 位置开餐馆的最大利润 (开和不开的最大值)
        dp[i] = max(dp[i-1], p[i-1] + dp[j])

    return dp[n]

# 主程序处理输入
t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    m = list(map(int, input().split()))
    p = list(map(int, input().split()))
    print(max_profit(n, k, m, p))

04118: 开餐馆 ​

04118: 开餐馆