回顾多重背包

有n种物品，用大小为m的包来装，问获取的最大价值为多少。其中，第 i 种物品的重量，价值，个数分别为 w[i],v[i],c[i].

那么，若f[i][j]表示考虑前 i 种物品，使用 j 的背包可获取的最大价值，状态转移方程为

for(int i=1;i<=n;i++)

　　for(int k=1;k<=c[i];k++)

　　　　for(int j=0;j<=m;j++)

　　　　　　if(j-k*w[i]>=0)f[i][j]=max(f[i-1][j],f[i-1][j-k*w[i])+v[i]);

　　　　　　else f[i][j]=f[i-1][j];

单调队列优化

考虑到，f[i][j1]可由f[i-1][j2]更新当且仅当j1,j2模w[i]同余。

那么，要更新每个f[i][j]，只用在 j' 模w[i]同余地一系列f[i-1][j']中找，而且这一系列数的 j' 有都相差w[i]，所以可以用一个单调队列来保存离 j 最近的c[i]个 j' 的最大值，队首保存用于更新的最优解，就可以直接找到最优的更新方案。

对于进队的条件：

由于放同一种物品空间与价值成正比，则f[i-1][j]可以更新的背包空间为一条斜线段所覆盖的区域，起点即为点(j,f[i-1][j])，斜率即为价值比总量，而队中存的就是起点（我存了起点的横坐标）。若当前有要入队的起点，可以做如第一个图的比较，使用当前起点更新的范围是否涵盖了队尾元素，若涵盖了则弹出，否则将当前起点加入队中。

对于出队条件：当前要更新的背包空间已经超出了队首的最远更新范围。

HDU2191代码

这个题其实可以不加优化：-）

1 #include
     
       2 using namespace std; 3 int C,n,m,a[101],b[101],c[101],f[101][101]; 4 int dui[100000],hd,tl; 5  6 bool calc(int kj,int wp) 7 { 8     int maxa=c[wp]*a[wp]; 9     int tem=dui[hd+1];10     if(tem+maxa