hdu 2191（单调队列优化多重背包模板）
hhz6830975
2018-02-25 14:28:44
[题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=2191)
裸的多重背包，数据也很水，只是打个模板用的
一般的多重背包时间复杂度$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$的范围
具体实现见代码
```cpp
#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;
}
```