1 条题解
-
0
C 神秘合金 (medal)
首先,定义
dp[sum, u]表示从节点 1 到节点 的路径中,经过的所有边的 总和为sum时,路径的 总和的最小值。我们的目标是从节点 1 到节点 ,找到使性能值最小的路径,性能值为:在这个过程中,状态转移的关键是根据边的属性 更新状态。
具体地,如果当前在节点 ,通过一条边 转移到节点 ,并且该边的 和 分别为 和 ,那么状态转移方程可以表示为:
$$dp[\text{sum} + a][v] = \min(dp[\text{sum} + a][v], dp[\text{sum}][u] + b)$$说明:
- 其中 表示当前路径的 总和。
- 通过边 ,新的路径的 总和为 ,路径的 总和为 。
这个方程的含义是:当我们从节点 转移到节点 时,如果当前路径的 总和为
sum,我们就将这个新的路径的 总和 和新的 总和 更新到状态 。注意到 时,状态相同的情况之间没有转移:
由于题目中规定 ,即每条边的 值都是正整数。因此,当前路径的 总和会随着每一次转移而增加,不能减少。
- 假设某条路径经过了节点 和节点 ,且路径的 。
- 当我们通过边 转移时,新的路径的 会变为 (因为 ),而 一定会增加。
- 因为 增加,且每个状态的 之间是严格递增的,所以在计算 时,如果某个状态的 已经确定了一个值,那么我们就可以直接从小的 值开始枚举,从而避免不必要的重复计算。
因此,状态之间不可能相同的情况会导致我们不需要转移到相同的 值。换句话说,路径的 总和的变化是单调递增的,因此状态间不会有相同的 值进行转移。
时间复杂度为
- 1
信息
- ID
- 219
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者