http://blog.csdn.net/xiaoxiaoluo/article/details/7802021
【单调队列优化】DP专题 - 数一新天地
题意：有n种硬币以及对应的数量
，问能组成1~m的总价值中的多少种。
当成01背包做是O(m∑C)，TLE！
二进制优化的方法是O(m∑logC)。。。貌似把常数优化一下下就能过。
然后就是单调队列优化了。O(nm)，和普通的01背包一样复杂度！
Read full article from 【单调队列优化】DP专题 - 数一新天地
若用dyna[i][j]表示背包容量为j，物品数为i的最大价值，多重背包的状态转移方程是
dyna[i][j] = max{ dyna[i - 1][j - k * w[i]] + k * c[i] } (0 ≤ k ≤ s[i])
k, c, s分别表示物品的费用，价值和数量。
直接这样上的话，复杂度可是O(VNM)。所以说考虑到方程“向前找”的特性，可以用单调队列来优化状态转移。
首先，单调队列中存放的是前面的价值和容量。为什么还要把容量存进去呢？我们把方程变个形看看：
dyna[i][j] = max{ dyna[i - 1][place] + (j - place) / w[i] * c[i] } (place >= j - w[i] * s[i])
dyna[i - 1][place]的值永远都不会变，但是根据place的不同，在dyna[i][j]处所能转移到的值也不一样。所以说必须把容量也存进去才能正确转移。
按照单调队列的特性，每次把新的dyna[i - 1][j - k * w[i]]的值进队，把老的值出队，之后取首个元素就可以了。然而循环的时候顺序要改变，如果要使用单调队列，循环的步长一定是w[i]。那么与首元素对w[i]取模的值不一样的元素就不能更新。要解决这个问题很简单——只需要用两个循环就可以了。模式如下：
for (j = 0; j < w[i]; j++)
{
for (k = j; k <= m; k += w[i])
{
// 状态转移
}
}
{
for (k = j; k <= m; k += w[i])
{
// 状态转移
}
}
至此这个问题就基本解决了。然而，单纯的O(VN)的多重背包要过这个题还是有点困难，必须进一步优化才可以。
【单调队列优化】DP专题 - 数一新天地
题意：有n种硬币以及对应的数量
，问能组成1~m的总价值中的多少种。当成01背包做是O(m∑C)，TLE！
二进制优化的方法是O(m∑logC)。。。貌似把常数优化一下下就能过。
然后就是单调队列优化了。O(nm)，和普通的01背包一样复杂度！
先从最本质开始想，
是多重背包的递推式子，dp[i][j]表示前i个物品在体积j的包中的最大价值。每次要O(C[i])才能转移一次，太慢了~！所以现在需要找到一种方法实现O(1)转移。
是多重背包的递推式子，dp[i][j]表示前i个物品在体积j的包中的最大价值。每次要O(C[i])才能转移一次，太慢了~！所以现在需要找到一种方法实现O(1)转移。
如果能把递推式子变成
那么就可以用单调队列在O(1)的情况下求出
的转移。
那么就可以用单调队列在O(1)的情况下求出的转移。
回到
，我们可以对j按模
进行分类:
,
, 
, ... ,
.
，我们可以对j按模进行分类:,, , ... ,.
于是可以表示成
的形式，
的形式，
设
, 则
,注意到
与
无关，可以放到外，
.
, 则,注意到与无关，可以放到外，.
设
,那么上面的式子就等价为
.
,那么上面的式子就等价为.
于是就是单调队列的形式！
Read full article from 【单调队列优化】DP专题 - 数一新天地
