单调队列优化多重背包

思路 首先我们考虑一下朴素的多重背包写法： 对于当前物品i，枚举选的个数n[i]，用于更新dp数组 然后我们能够发现这样一个神必规律： dp[i]用于维护代价为i的最大价值，且当前考虑选的物品代价为v 则dp[i]只能够从dp[j]，当且仅当j mod v == i mod v 且选的个数 ...
2021-11-05 00算法 > DP