1 条题解

  • 0
    @ 2026-11-15 22:43:21

    C 神秘合金 (medal)

    首先,定义 dp[sum, u] 表示从节点 1 到节点 uu 的路径中,经过的所有边的 aia_i 总和为 sum 时,路径的 bib_i 总和的最小值。我们的目标是从节点 1 到节点 NN,找到使性能值最小的路径,性能值为:

    (∑i∈Pai)×(∑i∈Pbi)(\sum_{i \in P} a_i) \times (\sum_{i \in P} b_i)

    在这个过程中,状态转移的关键是根据边的属性 (ai,bi)(a_i, b_i) 更新状态。

    具体地,如果当前在节点 uu,通过一条边 (u→v)(u \to v) 转移到节点 vv,并且该边的 aia_i 和 bib_i 分别为 aa 和 bb,那么状态转移方程可以表示为:

    $$dp[\text{sum} + a][v] = \min(dp[\text{sum} + a][v], dp[\text{sum}][u] + b)$$

    说明:

    • 其中 sum\text{sum} 表示当前路径的 aia_i 总和。
    • 通过边 (u→v)(u \to v),新的路径的 aia_i 总和为 sum+a\text{sum} + a,路径的 bib_i 总和为 dp[sum][u]+bdp[\text{sum}][u] + b。

    这个方程的含义是:当我们从节点 uu 转移到节点 vv 时,如果当前路径的 aia_i 总和为 sum,我们就将这个新的路径的 aia_i 总和 sum+a\text{sum} + a 和新的 bib_i 总和 dp[sum][u]+bdp[\text{sum}][u] + b 更新到状态 dp[sum+a][v]dp[\text{sum} + a][v]。

    注意到 ai>0a_i > 0 时,状态相同的情况之间没有转移:

    由于题目中规定 ai>0a_i > 0,即每条边的 aia_i 值都是正整数。因此,当前路径的 ∑ai\sum a_i 总和会随着每一次转移而增加,不能减少。

    • 假设某条路径经过了节点 uu 和节点 vv,且路径的 ∑ai=sum\sum a_i = \text{sum}。
    • 当我们通过边 (u→v)(u \to v) 转移时,新的路径的 ∑ai\sum a_i 会变为 sum+a\text{sum} + a(因为 ai>0a_i > 0),而 ∑ai\sum a_i 一定会增加。
    • 因为 ∑ai\sum a_i 增加,且每个状态的 ∑ai\sum a_i 之间是严格递增的,所以在计算 dpdp 时,如果某个状态的 ∑ai\sum a_i 已经确定了一个值,那么我们就可以直接从小的 ∑ai\sum a_i 值开始枚举,从而避免不必要的重复计算。

    因此,状态之间不可能相同的情况会导致我们不需要转移到相同的 ∑ai\sum a_i 值。换句话说,路径的 ∑ai\sum a_i 总和的变化是单调递增的,因此状态间不会有相同的 ∑ai\sum a_i 值进行转移。

    时间复杂度为 O(N⋅M⋅max(ai))O(N \cdot M \cdot \text{max}(a_i))

    • 1

    信息

    ID
    219
    时间
    2000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者