题意
原题题意描述就足够清楚，这里不再重述。
思路
第一眼就能看出这是一个经典的 01 背包，但是观察数据范围就可以发现：如果使用正常以体积作为 dp 的一维的话绝对会 MLE，我们需要找到别的出路。
再次观察数据，注意到 n≤500,ai≤500n \le 500 , a_i \le 500n≤500,ai ≤500，攻击力点数一定是小于等于 250000250000250000 的。看到这我们考虑，既然不能把体积当作 dp 维度，那么反过来，把攻击力当作维度不就好了。
设 dpidp_idpi 为当攻击力为 iii 时，所需要的最小金币数量。
初始状态：
dp0=0,dpi=INF∈{1,250000}dp_0 = 0,dp_i = INF \in \{1 , 250000\} dp0 =0,dpi =INF∈{1,250000}
转移方程：
设 iii 为正在转移的物体，jjj 为现在正在转移的增加的攻击力。
dpj=min(dpj,dpj−ai+ci)dp_j = \min(dp_j , dp_{j - a_i} + c_i) dpj =min(dpj ,dpj−ai +ci )
最后从大到小遍历，直到 dpi≤kdp_i \le kdpi ≤k 后输出 iii 即可。
AC CODE
