Problem F: 最优找零II

上一题 正确率: $70.50\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $2078$ 正确数量 $1465$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划 贪心

Description

假设货币有1,2,4,5,10五种硬币，每种数量都无限多，现在给出金额n(1<=n<=1000000)，求出最少的硬币数量

Input

现在给出金额n(1<=n<=1000000）

Output

最少的硬币数量

Sample Input复制

10

Sample Output复制

1

提示

动态规划