题解：P16300 [蓝桥杯 2026 省 Python C 组] 智能产线排程优化

yz19 · 2026-04-25 15:42:33 · 题解

题解：P16300 [蓝桥杯 2026 省 Python C 组] 智能产线排程优化

01 背包问题。

解题思路

这道题只要把订单截止时间升序排序，然后把最大收益记下来就行了。

最核心的变量就是 dp[a][b]，表示 A 线干了 a 分钟，B 线干了 b 分钟时，最多能赚多少钱。

然后遍历每个订单 (p, d, r)（耗时 p，截止 d，利润 r），倒着遍历表格：

• 不接单，那就是收益不变，可以直接跳掉。
• 交给了 A 线，如果 A 线已经做了 a 分钟，加上这个订单的耗时后还是没超过截止时间，那就接单，收益就加上 r。
• 交给了 B 线，如果 B 线已经做了 b 分钟，加上这个订单的耗时后还是没超过截止时间，那就接单，收益就加上 r。（跟 A 线是一样的，其实我这两行字是复制的 A 线 QAQ）

但是，数据范围还是太大了，得用 PyPy（想看纯 Python 的请移步）。

代码如下

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    jobs = []
    for _ in range(N):
        p = int(data[idx]); idx += 1
        d = int(data[idx]); idx += 1
        r = int(data[idx]); idx += 1
        jobs.append((p, d, r))
    jobs.sort(key=lambda x: x[1])
    max_d = 1000
    INF = -10**18
    dp = [[INF] * (max_d + 1) for _ in range(max_d + 1)]
    dp[0][0] = 0
    for p, d, r in jobs:
        for a in range(max_d, -1, -1):
            for b in range(max_d, -1, -1):
                if dp[a][b] < 0:
                    continue
                if a + p <= d and a + p <= max_d:
                    if dp[a][b] + r > dp[a + p][b]:
                        dp[a + p][b] = dp[a][b] + r
                if b + p <= d and b + p <= max_d:
                    if dp[a][b] + r > dp[a][b + p]:
                        dp[a][b + p] = dp[a][b] + r
    ans = 0
    for a in range(max_d + 1):
        for b in range(max_d + 1):
            if dp[a][b] > ans:
                ans = dp[a][b]
    print(ans)
if __name__ == "__main__":
    solve()

题解制作不易！！！点个赞再走嘛 QAQ