多重背包题目已经很熟了
我们要把它优化到O（nm）
也就是对于每一个物品，我们只能够对dp数组进行一次遍历，并且不能枚举取几个物品
或者说是，要在每一个状态下O（1）的找到取不同数量物品的最优解，并转移
我们可以发现，其实转移的区间是非常有规律的，f[j]只能够从f[j-v[i]]，f[j-2*v[i]]....f[j-c[i]*v[i]]这几个状态转移
也就是一个有间隔的区间的最大值，如果区间范围是固定的，很明显是O（m）可以解决的
但是区间的范围是在单调的向左移动的，那就是对于每一个情况开一个单调队列就好
主要是观察转移的规律，抽象这个过程，发现特点，然后优化掉不必要的计算
比如这里就是优化掉了对每一个j的向前遍历寻找最优转移的操作，而是考虑直接动态维护这个决策区间的最大值
也就是所谓的O（1）转移
这也算是单调队列优化dp转移的一个本质了
只是这个复杂一些，开的空间多一些而已
没区别
整个单调队列优化dp的模型就是
f[i]=min(f[j]+val(i,j))(L[i]<=j<=R[i]),然后L,R是单调的,所有的单调队列优化dp都是从这个式子来的，只是一些变形，或者是添加一些复杂的东西
（比如那个平衡树和多重背包的多个单调队列）
但是如果拆开，还是这个式子
单调队列优化里面的val(i,j)拆开后，每一项都只能和i和j中的一个有关，否则维护的东西就只能对现在的状态有用，对于后面的转移则是没有帮助，那也没有优化的必要的了
说这个，其实是因为，其实这种也能维护，但是使用的不再是单纯的单调队列了
标签：背包,队列,单调,优化,转移,dp From： https://www.cnblogs.com/HLZZPawa/p/17847569.html