Hướng dẫn giải của duong3982oj Contest 03 - Giáng sinh
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Subtask 1: ~K = 1~.
Với subtask này, nếu ~N~ chia hết cho ~a_1~, đáp án là ~\frac {N}{a_1}~.
Ngược lại, đáp án là ~-1~.
Độ phức tạp: ~O~ (~1~).
Subtask 4: ~N \le 10^5~.
Nếu ~N \le 10^5~, ta có thể dễ dàng quy hoạch động:
- Gọi ~f_i~ là số đồng xu tối thiểu để có ~i~ đồng.
- Ban đầu ~f_0 = 0~, ~f_i = inf~.
- Ta có ~f_i~ ~=~ ~min~ ~(f_{i - a_j} + 1)~ với mọi ~1 \le j \le K~ và ~i \ge a_j~.
- Kết quả nằm ở ~f_N~, và ta dễ dàng truy vết.
Độ phức tạp: ~O~ (~N \times K~).
Subtask 5: ~N \le 10^{18}~.
Bây giờ, chúng ta cần giải quyết dữ liệu lớn hơn.
Nhận xét: Chúng ta sẽ tham lam lấy đồng xu giá trị lớn nhất, cho đến khi số tiền còn lại đủ nhỏ, để ta có thể quy hoạch động.
Ở đây, ta có thể tham lam lấy đồng xu ~a_K~ đến khi ~N = 10^6~, sau đó quy hoạch động.
Độ phức tạp: ~O~ (~10^6 \times K~).
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"
const int N = 2e6 + 9;
int n, k, a[N];
int added = 0;
int trace[N];
int dp[N];
int idx[N];
int res[N];
signed main (){
ios_base::sync_with_stdio (false);
cin.tie (NULL);
cout.tie (NULL);
if (fopen ("input.txt", "r")){
freopen ("input.txt", "r", stdin);
freopen ("output.txt", "w", stdout);
}
cin >> n >> k;
for (int i = 1; i <= k; i++){
cin >> a[i];
idx[a[i]] = i;
}
if (n > 1e6){
added += (n - 1e6) / a[k];
n -= added * a[k];
}
for (int i = 1; i <= n; i++) dp[i] = 1e18 + 9;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= k; j++) if (i >= a[j]){
if (dp[i] > dp[i - a[j]] + 1){
dp[i] = dp[i - a[j]] + 1;
trace[i] = i - a[j];
}
dp[i] = min (dp[i], dp[i - a[j]] + 1);
}
}
if (dp[n] == 1e18 + 9){
cout << -1;
return 0;
}
cout << dp[n] + added << '\n';
int x = n;
while (x != 0){
int cc = trace[x];
cc = x - cc;
res[idx[cc]]++;
x = trace[x];
}
res[k] += added;
for (int i = 1; i <= k; i++) cout << res[i] << ' ';
}
Bình luận