Giả sử chúng ta có năm số, N, A, B, C, D. Chúng ta bắt đầu bằng số 0 và kết thúc bằng N. Chúng ta có thể thay đổi một số bằng một số đồng xu nhất định bằng các thao tác sau -
- Nhân số với 2, trả A xu
- Nhân số với 3, trả B xu
- Nhân số với 5, trả C xu
- Tăng hoặc giảm số đi 1, trả D xu.
Chúng tôi có thể thực hiện các thao tác này bất kỳ số lần nào theo bất kỳ thứ tự nào. Chúng tôi phải tìm số xu tối thiểu mà chúng tôi cần để đạt được N
Vì vậy, nếu đầu vào giống như N =11; A =1; B =2; C =2; D =8, thì đầu ra sẽ là 19, vì Ban đầu x là 0.
Đối với 8 đồng xu tăng x 1 (x =1).
Đối với 1 đồng xu, nhân x với 2 (x =2).
Đối với 2 xu, nhân x với 5 (x =10).
Đối với 8 xu, hãy tăng nó lên 1 (x =11).
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
Define one map f for integer type key and value Define one map vis for integer type key and Boolean type value Define a function calc, this will take n if n is zero, then: return 0 if n is in vis, then: return f[n] vis[n] := 1 res := calc(n / 2) + n mod 2 * d + a if n mod 2 is non-zero, then: res := minimum of res and calc((n / 2 + 1) + (2 - n mod 2)) * d + a) res := minimum of res and calc(n / 3) + n mod 3 * d + b if n mod 3 is non-zero, then: res := minimum of res and calc((n / 3 + 1) + (3 - n mod 3)) * d + b) res := minimum of res and calc(n / 5) + n mod 5 * d + c if n mod 5 is non-zero, then: res := minimum of res and calc((n / 5 + 1) + (5 - n mod 5)) if (res - 1) / n + 1 > d, then: res := n * d return f[n] = res From the main method, set a, b, c and d, and call calc(n)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
int A = 1;
int B = 2;
int C = 2;
int D = 8;
cout << solve(N, A, B, C, D) << endl;
} Đầu vào
11, 1, 2, 2, 8
Đầu ra
19