Chương trình C++ đếm số phép toán tối thiểu để đạt N bằng cách trả xu

Cho năm số N, A, B, C, D. Bắt đầu từ số 0, mục tiêu là đạt đến N. Có thể thực hiện các phép toán sau với chi phí tương ứng:

• Nhân số hiện tại cho 2, tốn A xu.
• Nhân số hiện tại cho 3, tốn B xu.
• Nhân số hiện tại cho 5, tốn C xu.
• Tăng hoặc giảm số hiện tại 1 đơn vị, tốn D xu.

Có thể thực hiện các phép toán bất kỳ số lần và theo bất kỳ thứ tự nào. Hãy tìm số xu tối thiểu cần để đạt N.

Ví dụ

Với N = 11; A = 1; B = 2; C = 2; D = 8, đầu ra là 19. Giải thích: tăng 1 (8 xu) → 1; nhân 2 (1 xu) → 2; nhân 5 (2 xu) → 10; tăng 1 (8 xu) → 11. Tổng = 19.

Giải thuật

Sử dụng đệ quy có nhớ (memoization) kết hợp với quy hoạch động. Hàm calc(n) trả về chi phí tối thiểu để đạt n từ 0. Tại mỗi bước, xem xét các lựa chọn: chia cho 2, 3, 5 (nghịch đảo của nhân) và điều chỉnh bằng phép cộng/trừ 1 để chia hết. Cập nhật kết quả tối thiểu.

Mã C++

#include <bits/stdc++.h>
using namespace std;

int a, b, c, d;
map<long, long> f;
map<long, bool> vis;

long calc(long n) {
    if (!n) return 0;
    if (vis.find(n) != vis.end()) return f[n];
    vis[n] = 1;
    long res = calc(n / 2) + n % 2 * d + a;
    if (n % 2)
        res = min(res, calc(n / 2 + 1) + (2 - n % 2) * d + a);
    res = min(res, calc(n / 3) + n % 3 * d + b);
    if (n % 3)
        res = min(res, calc(n / 3 + 1) + (3 - n % 3) * d + b);
    res = min(res, calc(n / 5) + n % 5 * d + c);
    if (n % 5)
        res = min(res, calc(n / 5 + 1) + (5 - n % 5) * d + c);
    if ((res - 1) / n + 1 > d)
        res = n * d;
    return f[n] = res;
}

int solve(int N, int A, int B, int C, int D) {
    a = A; b = B; c = C; d = D;
    return calc(N);
}

int main() {
    int N = 11, A = 1, B = 2, C = 2, D = 8;
    cout << solve(N, A, B, C, D) << endl;
}

Đầu vào / Đầu ra

Input: 11, 1, 2, 2, 8
Output: 19