[bzoj1531][POI2005]Bank notes
Description
拥有一套先进的货币系统,这个系统一共有
种面值的硬币,面值分别为
.但是每种硬币有数量限制,现在我们想要凑出面值
求最少要用多少个硬币.
Input
第一行一个数.
第二行个整数
.
第三行个整数
,表示每种硬币的个数.
最后一行一个数,表示要凑的面值数量.
Output
一行一个数,表示最少需要付的硬币数.
Sample Input
32 3 5
2 2 1
10
Sample Output
3
HINT
Solution
表示用前
种硬币凑出价值
所需最少硬币数.
对于对取模结果相同的
,可以用单调队列进行优化.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 205 #define M 20005 using namespace std; int f[N][M],b[N],c[N],q[M],h,t,n,m; inline void init(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&b[i]); for(int i=1;i<=n;++i) scanf("%d",&c[i]); scanf("%d",&m); for(int i=0;i<=n;++i) for(int j=1;j<=m;++j) f[i][j]=M; for(int i=1;i<=n;++i){ for(int k=0;k<b[i];++k){ h=1;t=0; for(int j=k;j<=m;j+=b[i]){ while(h<=t&&(j-q[h])/b[i]>c[i]) ++h; q[++t]=j; while(h<t&&f[i-1][q[t]]<=f[i-1][q[t-1]]+(j-q[t-1])/b[i]){ q[t-1]=q[t];--t; } f[i][j]=min(f[i-1][q[h]]+(j-q[h])/b[i],M); } } } printf("%d ",f[n][m]); } int main(){ freopen("bag.in","r",stdin); freopen("bag.out","w",stdout); init(); fclose(stdin); fclose(stdout); return 0; }