Hướng dẫn giải của Câu 2 (Tuyển sinh chuyên Tin Bình Dương 2023-2024)
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.
Hướng dẫn giải
Đếm số cách ghép tranh: số cách viết N thành tổng các số hạng từ 1 đến K (thứ tự có ý nghĩa).
Sub 1: Vét cạn đệ quy, ~O(2^N)~ (N ≤ 20)
Duyệt đệ quy mọi cách chọn số hạng tiếp theo. Đúng 29/50 test (các test lớn quá giờ).
Sub 2: Quy hoạch động, ~O(N K)~
dp[i] là số cách có tổng i, dp[i] = tổng của dp[i-j] với j = 1..min(K, i), dp[0] = 1. Đúng 50/50 test.
Chương trình hoàn chỉnh
main: N ≤ 20 gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int N, K;
long long cnt1;
// Sub 1: vet can. Duyet de quy moi cach viet N thanh tong cac so hang (moi so hang tu 1 den K)
void dfs(int rem) {
if (rem == 0) {
cnt1++;
return;
}
for (int j = 1; j <= min(K, rem); j++) dfs(rem - j);
}
void sub1() {
cnt1 = 0;
dfs(N);
cout << cnt1 << "\n";
}
// Sub 2: quy hoach dong. dp[i] = so cach ghep tranh co tong i; dp[i] cong tong dp[i-j], j = 1..min(K, i).
void sub2() {
vector<long long> dp(N + 1, 0);
dp[0] = 1;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= min(K, i); j++) dp[i] += dp[i - j];
cout << dp[N] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K;
if (N <= 20) sub1(); // N nho: vet can
else sub2(); // N lon: quy hoach dong
return 0;
}
Bình luận