加速优化问题

题目分析

一条物流路线有 个中转段，每段有若干运输方式可选，每种方式有延误风险和费用。需要为每段选择恰好一种运输方式，使所有段的延误风险之和不超过阈值 ，且总费用最小。

思路

拿到这道题，第一反应是枚举所有组合，但如果每段有 种选择、共 段，枚举量是 ，显然不可行。

仔细观察，这本质上是一个带约束的多阶段决策问题——每一段做一次选择，累积风险不超过 ，总费用最小。自然联想到背包类 DP。

但和经典背包不同的是，这里的"容量"（风险）是浮点数，没法直接开数组做背包。怎么办？

关键思路是：我们不需要对风险值做离散化，而是直接维护一组 Pareto 最优状态。

什么是 Pareto 剪枝？

处理完前若干段后，每种可行选择方案对应一个 二元组。如果方案 A 的风险不低于方案 B、费用也不低于方案 B，那 A 永远不可能比 B 更优，可以直接淘汰。

具体做法：

1. 初始状态 ，表示还没选任何段时风险为 0、费用为 0。
2. 每处理一段，将当前所有状态与该段所有选项做笛卡尔积，生成新状态。
3. 可行性剪枝：丢弃风险超过 的状态。
4. Pareto 剪枝：将状态按风险升序排列，只保留费用严格递减的前缀。因为风险更高但费用不更低的状态，在后续决策中不可能胜出。

最终，所有保留状态中费用最小的就是答案。

样例验证

以样例 1（）为例：

• 初始：
• 处理第 1 段后： 和 ，两者构成 Pareto 前沿（风险低的费用高，风险高的费用低）
• 处理第 2 段：将上述 2 个状态分别与第 2 段的 2 个选项组合，得到 4 个候选：

- , , ,

- 其中 风险超限，淘汰

- Pareto 剪枝后保留 ,

• 最小费用 ，与答案一致

代码

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    L = int(input_data[idx]); idx += 1
    T = float(input_data[idx]); idx += 1

    # dp: Pareto 最优的 (risk, cost) 列表
    dp = [(0.0, 0.0)]

    for _ in range(L):
        K = int(input_data[idx]); idx += 1
        options = []
        for _ in range(K):
            name = input_data[idx]; idx += 1
            risk = float(input_data[idx]); idx += 1
            cost = float(input_data[idx]); idx += 1
            options.append((risk, cost))

        new_states = []
        for r0, c0 in dp:
            for ri, ci in options:
                nr = r0 + ri
                nc = c0 + ci
                if nr <= T + 1e-9:
                    new_states.append((nr, nc))

        # Pareto 剪枝：按风险排序，保留费用严格递减的状态
        new_states.sort()
        pruned = []
        min_cost = float('inf')
        for r, c in new_states:
            if c < min_cost - 1e-9:
                pruned.append((r, c))
                min_cost = c
        dp = pruned

    ans = min(c for r, c in dp)
    print(f"{ans:.2f}")

main()

复杂度分析

• 时间复杂度：，其中 为 Pareto 前沿大小， 为每段的选项数。由于 Pareto 剪枝的存在， 远小于指数级。
• 空间复杂度：，存储当前 Pareto 状态集。