【BZOJ 1531】 [POI2005]Bank notes

1531: [POI2005]Bank notes

Time Limit: 5 Sec Memory Limit: 64 MB Submit: 271 Solved: 139 [Submit][Status][Discuss] Description

Byteotian Bit Bank (BBB) 拥有一套先进的货币系统,这个系统一共有n种面值的硬币,面值分别为b1, b2,…, bn. 但是每种硬币有数量限制,现在我们想要凑出面值k求最少要用多少个硬币.

Input

第一行一个数 n, 1 <= n <= 200. 接下来一行 n 个整数b1, b2,…, bn, 1 <= b1 < b2 < … < b n <= 20 000, 第三行 n 个整数c1, c2,…, cn, 1 <= ci <= 20 000, 表示每种硬币的个数.最后一行一个数k – 表示要凑的面值数量, 1 <= k <= 20 000.

Output

第一行一个数表示最少需要付的硬币数

Sample Input

3

2 3 5

2 2 1

10

Sample Output

3

队列优化的多重背包问题~

讲解详见【POJ 1742】

using namespace std;int a[M],c[M],f[M],n,m;struct Q{int x,y;}q[M];int main(){scanf(“%d”,&n);for (int i=1;i<=n;i++)scanf(“%d”,&a[i]);for (int i=1;i<=n;i++)scanf(“%d”,&c[i]);scanf(“%d”,&m);for (int i=1;i<=m;i++)f[i]=inf;f[0]=0;for (int i=1;i<=n;i++)for (int j=0;j<a[i];j++){int l=1,r=0;for (int k=0;k<=(m-j)/a[i];k++){int t=k*a[i]+j;while (l<=r&&q[l].x<k-c[i])l++;while (l<=r&&q[r].y>f[t]-k)r–;q[++r].x=k,q[r].y=f[t]-k;if (l<=r)f[t]=min(f[t],q[l].y+k);}}printf(“%d”,f[m]);return 0;}

，才能做到人在旅途，感悟人生，享受人生。