team2012-D1-sol-0045

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

本题是一道简单的dp, 注意到获得的分数都是整数, 如果考虑背包的话, 这个背包的容量最大是 MaxCapacity = N * MaxCredit * 100, 在本题里是 20 * 8 * 100 = 16000. 所以时间复杂度是 O(N*MaxCapacity*|ScoreRange|). 本来 ScoreRange 是 [0, 100], 但是观察得分公式可以知道这个范围实际上最大只有 [floor(a[i]*log(5)+b[i]), 100]. 由于 b >= 50, a >= 1, 所以 max(|ScoreRange|) <= 50. 所以估算一下是 10^7^ 的复杂度. 空间复杂度可以利用经典的背包降维的方法降到 O(MaxCapacity).

本题是一道简单的dp, 注意到获得的分数都是整数, 如果考虑背包的话, 这个背包的容量最大是 MaxCapacity = N * MaxCredit * 100, 在本题里是 20 * 8 * 100 = 16000. 所以时间复杂度是 O(N*MaxCapacity*|ScoreRange|). 本来 ScoreRange 是 [0, 100], 但是观察得分公式可以知道这个范围实际上最大只有 [floor(a[i]*log(5)+b[i]), 100]. 由于 b >= 50, a >= 1, 所以 max(|ScoreRange|) <= 50. 所以估算一下是 10⁷ 的复杂度. 空间复杂度可以利用经典的背包降维的方法降到 O(MaxCapacity).