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

某智能制造工厂拥有两条完全相同且可以并行工作的自动化生产线，分别记为 A 和 B。现在，工厂同时接到了 $N$ 份生产订单。 对于第 $i$ 份订单（$1 \le i \le N$），给定以下三个参数： - 加工时间 $p_i$：该订单在任意一条生产线上加工所需的时间； - 交付期限 $d_i$：该订单必须在第 $d_i$ 小时之前（含第 $d_i$ 小时）完成； - 订单收益 $r_i$：若该订单按时完成，工厂可以获得的收益。 两条生产线都从第 0 小时开始运行，并且彼此独立。对于任意一条生产线： - 同一时刻最多只能加工一份订单； - 每份订单一旦开始加工，就必须连续完成，不能中断； - 相邻订单之间没有切换时间。 工厂可以从这 $N$ 份订单中选择任意若干份进行生产。对于每一份被选择的订单，需要决定： - 将其分配给生产线 A 或生产线 B； - 它在对应生产线上的加工顺序。 要求所有被选择的订单都必须在各自的交付期限内完成。对此，请你计算：工厂最多能够获得多少收益。

第一行包含一个正整数 $N$，表示订单数量。 接下来 $N$ 行，每行包含三个正整数 $p_i, d_i, r_i$，分别表示第 $i$ 份订单的加工时间、交付期限和收益。

输出一行，包含一个整数，表示能够获得的最大总收益。

### 【样例说明 1】 四份订单的信息如下： | 订单编号 | $1$ | $2$ | $3$ | $4$ | |:---:|:-:|:-:|:-:|:-:| | 加工时间 $p_i$ | $3$ | $3$ | $2$ | $4$ | | 交付期限 $d_i$ | $4$ | $5$ | $3$ | $7$ | | 收益 $r_i$ | $10$ | $12$ | $6$ | $15$ | 一种最优安排如下： - 生产线 A：先加工订单 $3$，再加工订单 $2$； - 生产线 B：先加工订单 $1$，再加工订单 $4$。 具体完工情况为： - 生产线 A： - 订单 $3$ 在第 $0 \sim 2$ 小时加工，完工时刻为 $2$，满足 $2 \le d_3 = 3$； - 订单 $2$ 在第 $2 \sim 5$ 小时加工，完工时刻为 $5$，满足 $5 \le d_2 = 5$。 - 生产线 B： - 订单 $1$ 在第 $0 \sim 3$ 小时加工，完工时刻为 $3$，满足 $3 \le d_1 = 4$； - 订单 $4$ 在第 $3 \sim 7$ 小时加工，完工时刻为 $7$，满足 $7 \le d_4 = 7$。 四份订单均可按时完成，总收益为： $$ 6 + 12 + 10 + 15 = 43 $$ ### 【样例说明 2】 五份订单的总加工时间为： $$ 3 + 2 + 4 + 3 + 5 = 17 $$ 在最晚交付期限为 $8$ 的情况下，两条生产线在时间区间 $[0, 8]$ 内总共最多只能提供 $16$ 个单位的加工时间，因此不可能将全部订单都安排并按时完成。 一种最优方案是放弃订单 $2$，选择订单 $\{1, 3, 4, 5\}$。安排如下： - 生产线 A：先加工订单 $3$，再加工订单 $4$； - 生产线 B：先加工订单 $1$，再加工订单 $5$。 对应的完工时刻分别为： - 订单 $3$：完工时刻为 $4$，满足 $4 \le d_3 = 6$； - 订单 $4$：完工时刻为 $7$，满足 $7 \le d_4 = 7$； - 订单 $1$：完工时刻为 $3$，满足 $3 \le d_1 = 4$； - 订单 $5$：完工时刻为 $8$，满足 $8 \le d_5 = 8$。 这四份订单均能按时完成，因此总收益为： $$ 20 + 12 + 10 + 18 = 60 $$ 可以证明，不存在收益大于 $60$ 的可行方案，因此答案为 $60$。 ### 【评测用例规模与约定】 - 对于 $30\%$ 的评测用例，满足 $N \le 15$； - 对于 $60\%$ 的评测用例，满足 $N \le 50$，且 $d_i \le 300$； - 对于所有的评测用例，$1 \le N \le 200$，$1 \le p_i \le 50$，$p_i \le d_i \le 1000$，$1 \le r_i \le 10000$。