题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=1531
题解：
单调队列优化多重背包DP
（弱弱的我今天总算是把这个坑给填了。。。）
令V[i]为第i种硬币的面值，C[i]为第i种硬币的数目。
定义DP[i][j]表示用了前i种硬币，凑出面值为j的最小硬币数。
先看看这个题用最裸的背包是如何转移的：
DP[i][j]=min(dp[i-1][j-k*V[i]]]+k)
然后，我们令 a=⌊j÷V[i]⌋ (⌊ ⌋:向下取整)，b=j%V[i]
那么 j=a*V[i]+b
接下来这样考虑，对于一个当前计算的总面值j，
同样枚举k，但不再像之前那样表示选择了几个i号硬币，
而是表示相对于a而言，少选几个i号硬币。
换句话说，我们对于当前的j，在默认要选a个i号硬币基础上，去枚举少选k个该硬币。
那么怎样转移呢：
DP[i][j]=min(dp[i-1][b+K*V[i]]+a-k)
其实意思还是很明了的，就是选了 a-k 个i号硬币嘛。（好好理解一下）
然后可以把取小项里面的a提出来：
DP[i][j]=min(dp[i-1][b+K*V[i]]-k)+a
再看看这个式子，如果固定i和b，取小项里面就只有K是变化的，
把其看成是一个只与k有关的函数，
显然就可以用单调队列维护最小值然后O(1)转移啦。
具体做法是：
第一层循环先枚举硬币i，
第二层循环再枚举一个b值，
第三层循环接着枚举j，需要满足j=b+a*V[i]
然后第三层循环里面的转移就可以用单调队列维护了，
总的复杂度为 O(N*M)
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 205
#define MAXM 20005
using namespace std;
int V[MAXN],C[MAXN],DP[MAXN][MAXM];
int N,M;
int main(){
static int QK[MAXM],l,r;
scanf("%d",&N);
for(int i=1;i<=N;i++) scanf("%d",&V[i]);
for(int i=1;i<=N;i++) scanf("%d",&C[i]);
memset(DP,0x3f,sizeof(DP));
scanf("%d",&M);
DP[0][0]=0;
for(int i=1;i<=N;i++){
for(int b=0,a;b<V[i];b++){
l=1; r=0;
for(int j=b;a=j/V[i],j<=M;j+=V[i]){
while(l<=r&&DP[i-1][b+QK[r]*V[i]]-QK[r]>=DP[i-1][b+a*V[i]]-a) r--;
QK[++r]=a;
while(l<=r&&a-QK[l]>C[i]) l++;
DP[i][j]=DP[i-1][b+QK[l]*V[i]]-QK[l]+a;
}
}
}
printf("%d",DP[N][M]);
return 0;
}