hdu 2191(单调队列优化多重背包模板)

2018-02-25 14:28:44


题目链接

裸的多重背包,数据也很水,只是打个模板用的

一般的多重背包时间复杂度$O(V \sum N)$,二进制优化后$O(V \sum logN)$,但有的题必须$O(N \cdot V)$才能过,这就必须用单调队列优化了

设物品$i$体积$v[i]$,价值$w[i]$,个数$n[i]$

多重背包dp方程:

$$dp[i][j]=max \lbrace dp[i-1][j-k \cdot v[i]]+k \cdot w[i] \rbrace \qquad (0 \leq k \leq min(n[i],j/v[i]))$$

设$a=j/v[i]$,$b=j \% v[i]$,即$j=a \cdot v[i]+b$

在每一轮循环中$i$相同,即$v$、$w$、$n$都相同

dp方程变形为:

$$dp[i][a \cdot v+b]=max \lbrace dp[i-1][(a-k) \cdot v+b]+k \cdot w \rbrace \qquad (0 \leq k \leq min(n,a))$$

设$s=a-k$,那么$a-min(n,a) \leq s \leq min(n,a)$

代入dp方程得:

$$dp[i][a \cdot v+b]=max \lbrace dp[i-1][s \cdot v+b]-s \cdot w \rbrace +a \cdot w \qquad (a-min(n,a) \leq s \leq min(n,a))$$

令$f[x]=dp[i][x \cdot v+b]$,$g[x]=dp[i-1][x \cdot v+b]-x \cdot w$,$h[x]=x \cdot w$,那么上式即为:

$$f[a]=max \lbrace g[s] \rbrace +h[a] \qquad (a-min(n,a) \leq s \leq min(n,a))$$

用单调队列维护$g[s]$即可实现$O(1)$转移,要注意满足$s$的范围

具体实现见代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=110;
int C,N,M,dp[maxn];
int Q[maxn][2],head,tail;//Q[x][0]存g[s],Q[x][1]存s以判断s是否符合限制条件

int main(){
    scanf("%d",&C);
    while(C--){
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&N,&M);
        for(int i=1;i<=M;i++){
            int v,w,n;
            scanf("%d%d%d",&v,&w,&n);
            for(int b=0;b<v;b++){//枚举余数b
                head=tail=1;//清空队列,加在这里是因为只能从余数相同的状态转移来,之前队列中的元素都不需要了
                for(int j=0;j<=(N-b)/v;j++){
                    int tmp=dp[j*v+b]-j*w;//这里的dp是上一轮的,j代表s
                    while(head<tail&&tmp>=Q[tail-1][0]) --tail;//先插入以满足s≤min(n,a)的条件
                    Q[tail][0]=tmp,Q[tail++][1]=j;//这里j还是代表s
                    while(Q[head][1]<j-min(n,j)) ++head;//以下j代表a,删除队首以去除不满足a−min(n,a)≤s的状态
                    dp[j*v+b]=Q[head][0]+j*w;//队首即为最优
                }
            }
        }
        printf("%d\n",dp[N]);
    }
    return 0;
}