这道题所有购买方案的取值上界为\(a_i \times k\)，差不多就是\(1e5\)级别。考虑超级大暴力，设置状态\(f[i][j][w]\)为选了\(i\)个次、最后一次是第\(j\)种硬币且当前总价为\(w\)是否可行。这个转移算上取值上限就差不多是\(O(n^4)\)的，只能过掉一部分分数。
考虑进行状态转化。我们先让所有商品的价格减去价格最小值，然后剩下购买的方案就变成了形如\(k*minVal + sum\)的形式，然后我们设置状态\(f[i][j]\)最后一次选第\(i\)种商品，且选到\(j\)的最少选择次数，统计次数小于\(k\)的状态就可以了。
考虑超级暴力，设计状态\(dp[k][i][j]\)为走了\(k\)步处于\((i, j)\)的答案：
\[ dp[k][i][j] = mp[i][j] + \max \begin{cases} dp[k – 1][i – 1][j] \\ dp[k – 1][i + 1][j] \\ dp[k – 1][i][j + 1] \\ dp[k – 1][i][j – 1] \end{cases} \]
由于本人分治很菜，所以就来刷分治题了。
先思考 50 分\(O(n^2)\)的做法。记录每一个位置的原始值、变化后的最大值、变化后的最小值，然后发现如果一个位置\(i\)对后面的位置\(j\)有贡献当且仅当：
\[a_i < minVal_j \ (1) \\ maxVal_i < a_j \ (2) \]
所以这就相当于一个二位偏序的题目，有两个限制。我们可以用整体二分，在做完左区间之后，左区间按原来的值进行排序，而右区间按最小值进行排序，即可满足第一个条件；第二个条件可以用线段树来搞，搞两个指针来比较大小，然后用线段树来统计答案即可。非常好写。
这道题真的是令人窒息，也告诉了我比赛的时候上 QQ 是一个非常坏的习惯。
这道题 60 分做法非常之显然：相同体积的物品归为一种物品，且价值为同体积内最大的价值。这样就可以把物品数量压到 100 个以内。
但是这样是通过不了全部分数的，而且全部分数的容量非常之大，所以正常的 DP 优化是行不通的。做完上面的压缩之后，可以考虑做一些贪心进行优化。接下来我会详细的介绍这个贪心策略：
首先，这道题是概率和期望分开算的，进行 DP 时实质上是对概率进行 DP。考虑拆位，设\(dp_b [u]\)为从\(u \to n\)在第\(b\)位为\(1\)的概率，那么显然：
\[ dp_b[u] = \frac{1}{deg[u]}( \sum_{weight(u, v) !\& b} dp_b[v] \sum_{weight(u, v) \& b} (1 – dp_b[v]) ) \]
其中，\((1 – dp_b[v])\)为\(v\)为\(0\)的概率，最后答案消元完就是\(\sum_{i = 1} ans[i] 2^i\)。