Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [C] Đổi tiền với mệnh giá tuỳ chọn — số tờ ít nhất

    Cửa hàng có nnn loại mệnh giá c1,c2,…,cnc_1, c_2, \ldots, c_nc1​,c2​,…,cn​ (mỗi loại số lượng không giới hạn). Cần trả khách số tiền chính xác SSS đồng bằng ít tờ tiền nhất.

    Dùng DP: dp[i]=min⁡j:cj≤i(dp[i−cj]+1)dp[i] = \min_{j: c_j \le i} (dp[i - c_j] + 1)dp[i]=minj:cj​≤i​(dp[i−cj​]+1), với dp[0]=0dp[0] = 0dp[0]=0. Nếu không thể đổi, in −1-1−1.

    Ví dụ: c=[1,2,5]c = [1, 2, 5]c=[1,2,5], S=11S = 11S=11 → 5+5+1=115 + 5 + 1 = 115+5+1=11 dùng 333 tờ.

    • Định dạng đầu vào:

      Dòng 1: nnn, SSS. Dòng 2: nnn mệnh giá cic_ici​.

    • Ràng buộc đầu vào:

      1≤n≤1001 \le n \le 1001≤n≤100, 0≤S≤1040 \le S \le 10^40≤S≤104, 1≤ci≤1041 \le c_i \le 10^41≤ci​≤104.

    • Định dạng đầu ra:

      Một số nguyên — số tờ tối thiểu, hoặc −1-1−1 nếu không đổi được.

    Ví dụ:

    Đầu vào:

    3 11
1 2 5

    Đầu ra:

    3

    Giải thích:

    5+5+1 = 11 dùng 3 tờ.

    Đang tải editor...