ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
ContestProblemSetList
Login
Register
问题 R: 的货币系统Banknotes
内存限制:128 MB
时间限制:1 S
题面:传统
评测方式:文本比较
上传者:
提交:56
通过:11
返回比赛
提交
提交记录
题目描述
原题来自:POI 2005
Byteotian Bit Bank (BBB) 拥有一套先进的货币系统,这个系统一共有 n 种面值的硬币,面值分别为 b1,b2,...bn。但是每种硬币有数量限制,现在我们想要凑出面值 k,求最少要用多少个硬币。
输入格式
输入格式
第一行一个数 n;
接下来一行 n 个整数b1,b2,...bn;
第三行 n个整数 ,c1,c2,..cn表示每种硬币的个数;
最后一行一个数 kk,表示要凑的面值数。
输出格式
输出格式
第一行一个数表示最少需要付的硬币数。
输入样例
复制
3 2 3 5 2 2 1 10
输出样例
复制
3
分类标签
背包
acwing