A – 完全背包
这道题真的是令人窒息，也告诉了我比赛的时候上 QQ 是一个非常坏的习惯。
这道题 60 分做法非常之显然：相同体积的物品归为一种物品，且价值为同体积内最大的价值。这样就可以把物品数量压到 100 个以内。
但是这样是通过不了全部分数的，而且全部分数的容量非常之大，所以正常的 DP 优化是行不通的。做完上面的压缩之后，可以考虑做一些贪心进行优化。接下来我会详细的介绍这个贪心策略：
这道题真的是令人窒息，也告诉了我比赛的时候上 QQ 是一个非常坏的习惯。
这道题 60 分做法非常之显然：相同体积的物品归为一种物品，且价值为同体积内最大的价值。这样就可以把物品数量压到 100 个以内。
但是这样是通过不了全部分数的，而且全部分数的容量非常之大，所以正常的 DP 优化是行不通的。做完上面的压缩之后，可以考虑做一些贪心进行优化。接下来我会详细的介绍这个贪心策略：
今天被各路神仙吊打，顺利 gg。
在考场上我推了个有后效性的 DP，还以为是高斯消元，然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。
首先，对一个概率为\(p\)的事件，它的期望次数是\(\frac{1}{p}\)（参见这里）。然后，考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。
考虑\(dp[1]\)的求法，首先需要两个级别为\(0\)的武器，然后发现无论失败与否都可以保证至少又一个\(0\)级武器，所以我们只需要注意另外一个武器的花费就可以了：
\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]