题意
分析
- 注意到本题的 (C) 很小，考虑定义一个和 (C) 有关的状态。
- 记 (f(x,j)) 表示考虑到了价格为 (x) 的物品，一共花费了 (j) 元的最大收益。将价格为 (x) 的物品按照收益从大到小排序，记这个数组为 (w) ，不难发现我们选择的一定是 (w) 的一段前缀的形式。
- 将所有的 (j) 按照模 (x) 的余数分类，容易得到： (f(x,i)=maxlimits_{j\%x=i\%x}{f(x-1,j)+w(frac{i-j}{x})})
- 同类的位置决策单调，原因是 (w) 是一个关于两个位置的上凸的二元函数。证明仍然考虑假设决策不单调，(a<b<c<d)，就可以得到 (s(c-a)-s(c-b)<s(d-a)-s(d-b)) ，在平面直角坐标系中体现为两端 (x) 差相同的区间，靠后的区间 (y) 的差较小，容易证明假设不成立。