Đổi Tiền Ít Xu Nhất

Buổi 21 — DP 1D cổ điển Dynamic Programming dynamic-programming
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho $N$ loại tiền xu với các mệnh giá $c_1, c_2, \dots, c_N$ (số lượng mỗi loại không giới hạn) và một số tiền mục tiêu $S$. Hãy tìm số lượng đồng xu ít nhất cần dùng để tổng mệnh giá bằng đúng $S$. Nếu không thể đổi được, in ra -1.

Cấu trúc con tối ưu: $dp[x] = \min_{c_i \le x} (dp[x - c_i] + 1)$.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $S$ ($1 \le N \le 100$, $0 \le S \le 10^4$).
  • Dòng thứ hai chứa $N$ số nguyên dương $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 10^4$).
Dữ liệu ra
  • In ra số xu ít nhất cần dùng, hoặc -1 nếu không thể.
Ví dụ
Input Output
3 11\n1 2 5 3
1 3\n2 -1
Giới hạn
  • $1 \le N \le 100$
  • $0 \le S \le 10^4$
  • $1 \le c_i \le 10^4$
Draft saved