P5365 SNOI2017 英雄联盟

基本思路

刚洗完澡做的，脑子转不动了。

疑似开始自动化思考了，状态转移方程是这一坨\(F[i][j] *= F[i - 1][j - k * w[i]]\)

事实上根本不对。首先当前的方案数完全没有体现出来，只乘了之前的方案数，而且这是一个最优性问题，不是计数问题，要在两种状况中做出选择。

改进思路

\(F[i][j]\)来表示前\(i\)个皮肤的\(j\)个花费的最大方案数

其实和一开始一样，但是这里强调了最大方案数，而并非总方案数。

转移方程：

\(F[i][j] = max(F[i - 1][j], F[i - 1][j - k * w[i]] * k)\)

要么不选择展示当前皮肤，要么展示当前皮肤，并把上一个状态的方案数乘上当前展示的方案数。

最后由于是要找最少的花费，再跑一遍整个\(F\)，找到最小的\(j\)满足\(F[j] >= m\)