bzoj#P1716. [Usaco2006 Dec]The Fewest Coins 找零钱
[Usaco2006 Dec]The Fewest Coins 找零钱
题目描述
农夫 John 想到镇上买些补给。为了高效地完成任务,他想使硬币的转手次数最少。即使他交付的硬币数与找零得到的的硬币数最少。John 想要买 样东西。有 种货币参与流通,面值分别为 。John 有 个面值为 的硬币。我们假设店主有无限多的硬币,并总按最优方案找零。
输入格式
- Line :两个整数 与 。
- Line : 个数,表示 。
- Line : 个数,表示 。
输出格式
- Line :一个整数,表示最优方案的转手次数,如无解输出
-1
。
3 70
5 25 50
5 2 1
3
数据规模与约定
对于 的数据,,,,。
题目来源
Gold