Hướng dẫn giải của [2526 KS2 THCS] Bài 4: Chia lì xì [BAI4]
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
Gọi ~T~ là tổng các tờ tiền. Hai anh em chọn hai tập tờ tiền rời nhau có cùng tổng ~S~ lớn nhất có thể; phần dư ~L = T - 2S~. Mẹ thêm ~L~ rồi chia đều nên mỗi người được thêm ~L~ (khớp ví dụ 2: ~13 + 5 = 18~). Vậy mỗi người nhận ~S + L = T - S~, ta cần tìm ~S~ lớn nhất.
Sub 1: Vét cạn — ~O(n \cdot 3^n)~, dùng khi ~n \le 13~
Mỗi tờ thuộc An, thuộc Bình hoặc không ai nhận: duyệt ~3^n~ cách, lấy ~S~ lớn nhất khi hai tổng bằng nhau. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Quy hoạch động theo hiệu — ~O(n \cdot T)~
Gọi ~dp[d]~ là tổng lớn nhất của phần nhỏ hơn khi hai phần chênh nhau ~d~. Với mỗi tờ tiền ~v~: không chọn; cho vào phần lớn hơn (~d \to d+v~); hoặc cho vào phần nhỏ hơn (~d \to |d-v|~, cộng thêm ~v~ hoặc ~d~ vào phần nhỏ). Khi đó ~S = dp[0]~ và đáp án là ~T - dp[0]~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; ~n \le 13~ gọi sub1 (10 test), lớn hơn gọi sub2 (10 test). 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;
int c[505];
// Sub 1: vét cạn 3^n — mỗi tờ tiền thuộc An, thuộc Bình hoặc không chọn, dùng khi n <= 13
void sub1() {
long long total = 0, S = 0;
for (int i = 0; i < n; i++) total += c[i];
int p3 = 1;
for (int i = 0; i < n; i++) p3 *= 3;
for (int mask = 0; mask < p3; mask++) {
int x = mask;
long long a = 0, b = 0;
for (int i = 0; i < n; i++, x /= 3) {
int t = x % 3;
if (t == 1) a += c[i];
else if (t == 2) b += c[i];
}
if (a == b) S = max(S, a);
}
cout << total - S << "\n"; // mỗi người nhận S + (T - 2S) = T - S
}
// Sub 2: quy hoạch động theo hiệu — O(n * T)
// dp[d] = tổng lớn nhất của phần nhỏ hơn khi hai phần chênh lệch d
void sub2() {
int T = 0;
for (int i = 0; i < n; i++) T += c[i];
const int NEG = -1e9;
vector<int> dp(T + 1, NEG), nd;
dp[0] = 0;
for (int i = 0; i < n; i++) {
nd = dp; // không chọn tờ này
int v = c[i];
for (int d = 0; d <= T; d++) {
if (dp[d] == NEG) continue;
if (d + v <= T) nd[d + v] = max(nd[d + v], dp[d]); // đưa vào phần lớn hơn
if (v <= d) nd[d - v] = max(nd[d - v], dp[d] + v); // đưa vào phần nhỏ hơn, vẫn chưa vượt
else nd[v - d] = max(nd[v - d], dp[d] + d); // phần nhỏ trở thành phần lớn
}
dp = nd;
}
cout << T - dp[0] << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> c[i];
if (n <= 13) sub1();
else sub2();
return 0;
}
Bình luận