#A. 纸币问题 1

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \
    Type: RemoteJudge 1000ms 256MiB

纸币问题 1

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

某国有 nn 种纸币，每种纸币面额为 aia_i 并且有无限张，现在要凑出 ww 的金额，试问最少用多少张纸币可以凑出来？

输入格式

第一行两个整数 n,wn,w，分别表示纸币的种数和要凑出的金额。 第二行一行 nn 个以空格隔开的整数 a1,a2,a3,…ana_1, a_2, a_3, \dots a_n 依次表示这 nn 种纸币的面额。

输出格式

一行一个整数，表示最少使用的纸币张数。

样例 #1

样例输入 #1

6 15
1 5 10 20 50 100

样例输出 #1

2

样例 #2

样例输入 #2

3 15
1 5 11

样例输出 #2

3

提示

对于 40%40\% 的数据，满足 n≤10n\le 10，w≤100w\le 100； 对于 100%100\% 的数据，满足 1≤n≤1031\le n\le 10^3，1≤ai≤w≤1041\le a_i \leq w\le 10^4。

北辰OI俱乐部算法提高班：动态规划专题（一）

Not Claimed
Status
Done
Problem
28
Open Since
2023-11-25 0:00
Deadline
2024-12-26 23:59
Extension
24 hour(s)
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 38ms
  • Powered by Hydro v4.9.27 Community