Hướng dẫn giải của Bờm và phú ông
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
Chọn tập con các thỏi vàng có tổng trọng lượng lớn nhất không vượt quá ~S~ (một cái ba lô), đồng thời đếm số tập con đạt tổng lớn nhất đó (lấy dư ~10^9+7~ nếu ~Q = 2~). Đây là bài cái túi (knapsack) kết hợp đếm.
Sub 1: Vét cạn — ~O(2^n \cdot n)~, dùng khi ~n \le 20~
Duyệt mọi tập con của ~n~ thỏi vàng, tính tổng; tổng không vượt ~S~ thì cập nhật tổng lớn nhất và số cách.
Sub 2: Quy hoạch động cái túi — ~O(n \cdot S)~
Gọi ~cnt[s]~ là số tập con có tổng đúng ~s~; ~cnt[0] = 1~. Với mỗi thỏi vàng nặng ~a~, duyệt ~s~ từ ~S~ xuống ~a~: ~cnt[s] += cnt[s-a]~ (lấy dư). Vì số cách lấy dư có thể bằng 0 nên dùng thêm mảng đánh dấu ~ok[s]~ (có tập con tổng ~s~) để tìm tổng lớn nhất ~\le S~. Do ~n \cdot S \le 5 \cdot 10^6~ nên chạy rất nhanh.
Lưu ý: số cách có thể rất lớn (vượt cả số nguyên 64 bit), nên phải lấy dư ~10^9+7~ ngay sau mỗi phép cộng, nhân; nếu để tới cuối mới lấy dư thì kết quả đã bị tràn số và sai.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu (file PO.INP/PO.OUT); nếu ~n \le 20~ gọi sub1, ngược 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;
const long long MOD = 1000000007;
int n, S, Q, a[1005];
void in_kq(long long best, long long ways) {
cout << best << "\n";
if (Q == 2) cout << ways % MOD << "\n";
}
// Sub 1: duyệt mọi tập con — dùng khi n <= 20
void sub1() {
long long best = 0, ways = 0;
for (int mask = 0; mask < (1 << n); mask++) {
long long sum = 0;
for (int i = 0; i < n; i++) if (mask >> i & 1) sum += a[i];
if (sum > S) continue;
if (sum > best) best = sum, ways = 1;
else if (sum == best) ways++;
}
in_kq(best, ways);
}
// Sub 2: quy hoạch động cái túi, cnt[s] = số tập con có tổng đúng s — O(n*S)
void sub2() {
vector<long long> cnt(S + 1, 0);
cnt[0] = 1;
vector<char> ok(S + 1, 0);
ok[0] = 1;
for (int i = 0; i < n; i++)
for (int s = S; s >= a[i]; s--) {
cnt[s] = (cnt[s] + cnt[s - a[i]]) % MOD;
if (ok[s - a[i]]) ok[s] = 1;
}
int best = S;
while (!ok[best]) best--; // cnt có thể bằng 0 do chia dư nên dùng mảng ok
in_kq(best, cnt[best]);
}
int main() {
freopen("PO.INP", "r", stdin);
freopen("PO.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> S >> Q;
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 20) sub1();
else sub2();
return 0;
}
Bình luận