Hướng dẫn giải của CAU2
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
Số hình vuông ít nhất có tổng diện tích bằng ~S~ là bài toán quy hoạch động: ~dp[i] = \min_k (dp[i - k^2] + 1)~.
Sub 1: Quy hoạch động cho từng test — ~O(S \sqrt{S})~, dùng khi ~S \le 1000~
Với mỗi test, tính ~dp~ từ 0 đến ~S~ rồi in ~dp[S]~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Tính sẵn một lần — ~O(S_{max} \sqrt{S_{max}})~
Tính ~dp~ đến ~S_{max}~ một lần, sau đó trả lời mỗi test trong O(1).
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đọc hết các test; nếu ~S_{max} \le 1000~ dùng sub 1, còn lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
int T;
vector<int> S; // cac gia tri S cua cac test, dung chung cho cac sub
// Quy hoach dong: dp[i] = so hinh vuong it nhat co tong dien tich bang i. O(i * sqrt(i)).
int minSquares(int s) {
vector<int> dp(s + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= s; i++)
for (int k = 1; k * k <= i; k++)
dp[i] = min(dp[i], dp[i - k * k] + 1);
return dp[s];
}
// Sub 1: tinh rieng cho tung test bang DP. Dung khi moi S <= 1000.
void sub1() {
for (int s : S) cout << minSquares(s) << "\n";
}
// Sub 2: tinh DP mot lan cho moi S den max, roi tra loi O(1). Dung cho S den 10^4.
void sub2() {
int mx = 1;
for (int s : S) mx = max(mx, s);
vector<int> dp(mx + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= mx; i++)
for (int k = 1; k * k <= i; k++)
dp[i] = min(dp[i], dp[i - k * k] + 1);
for (int s : S) cout << dp[s] << "\n";
}
int main() {
cin >> T;
S.resize(T);
for (int i = 0; i < T; i++) cin >> S[i];
int mx = 0;
for (int s : S) mx = max(mx, s);
if (mx <= 1000) sub1();
else sub2();
return 0;
}
Bình luận