单调队列优化多重背包

在 O(n∗v) 的时间内求解多重背包

多重背包的转移方程：
f[j]=min{ f[j−k∗v[i]]+k∗w[i] }

对于这个转移方程我们看到这里： f[j−k∗v[i]]
也就是说 f[j] 的值是由且仅由 f[j−k∗v[i]] 转移过来的，而在这个转移方程中， v[i],w[i] 在i特定的情况下相对为常数
那么我们可以根据模 v[i] 下的意义来对所有的 f[j] 进行分类，对于每一类（如 f[j],f[j+v],f[j+2∗v],f[j+3∗v]...... ）

我们可以把这一类的元素看成一个序列
看到这样一个序列，我们非常希望让它满足单调队列的要求，这样就可以一遍过了
那么对于与 f[j+v] 同类的所有元素我们要怎么样才能让它满足单调性呢？
在这里我们称与 f[j+v] 同类的每一种元素为一种方案
那么就是方案与方案之间的转移，所以我们可以在队列中放：以该方案在最大体积的限制下最多能得到多少价值。
也就是这样：令当前物品最多能放x个，当前转移到 f[j+k∗v] ，那么我们把 f[j+k∗v]+(x−k)∗w 放入队列
为什么要最大体积的限制下呢？因为我们得到的 f[j+k∗v] 不是最大体积限制下的，那这就不公平了，我们考虑每一个方案是否为优等方案这应该让这些方案控制变量，即让体积限制均为最大体积。就好比假设人跑步都是平均速率，两个人比跑步，一个人平常练的路程较短，另一个人平常练的路程较长，我们显然是不可以根据他们的平时成绩来比较的，而是应该让他们跑相同的一段路程来比较时间

这样我们就可以维护一个单调队列了
对于队首我们根据当前枚举到的放k个物品的情况，令队首的是放了j个物品的方案，如果 k−j>该物品最多可以放的数量 ，那么就应该弹出队首
对于队尾我们根据当前新加入的方案来比较队尾方案与当前方案哪个更优，如果当前方案更优就弹出队尾
这样就维护好了一个单调队列

因为我们对所有这样的序列进行了一次操作，这些序列的总长度为v，所以最后的时间复杂度为 O(n∗v)

题目见：罗大师的采药

#include<cstdio>

#define For( i , _Begin , _End ) for( int i=_Begin;i<=_End;i++ )

template< typename Type >inline Type max ( Type x , Type y ){ return x > y ? x : y ; }
template< typename Type >inline Type min ( Type x , Type y ){ return x < y ? x : y ; }
template< typename Type >inline void Read( Type &In ){
    In=0;char ch=getchar();
for( ;ch> '9'||ch< '0';ch=getchar() );
for( ;ch>='0'&&ch<='9';ch=getchar() )In = In*10 + ch-'0';
}

static const int MAXN = 1e5 +1;

int n , q , t , v , x , c , M , tmp;
int Que[MAXN][2] , H , T;
int m[MAXN] , Sz[11][11];
int f[MAXN];

void Pack_with_queue(){
    For( I , 1 , 10 )For( J , 1 , 10 )
if( Sz[I][J] ){
            t = I;v = J;x = M / t;
            c = min( x , Sz[I][J] );
            For( j , 0 , t-1 ){
                H = T = 0;
                Que[0][1] = f[j] + x*v;
                For( k , 1 , x ){
int tmp = j + k*t;
if( tmp > M )break;
while( H <= T && k - Que[H][0] > c )H++;
while( H <= T && Que[T][1] <= f[ tmp ] + ( x-k )*v )T--;
                    T++;
                    Que[T][0] = k;Que[T][1] = f[ tmp ] + ( x-k )*v;
                    f[ tmp ] = max( f[ tmp ] , Que[H][1] - ( x-k )*v );
                }
            }
        }
}

#define Judge

int main(){

#ifdef Judge
        freopen("medic.in","r",stdin);
        freopen("medic.out","w",stdout);
#endif

    Read( n );Read( q );
    For( i , 1 , n )Read( t ) , Read( v ) , Sz[t][v]++;
    For( i , 1 , q )Read( m[i] ) , M = max( M , m[i] );

    Pack_with_queue();

    For( i , 1 , q )
printf("%d\n",f[m[i]]);
return 0;
}