Hướng dẫn giải của Thành phố
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu chọn các mảnh đất để xây dựng X trung tâm thương mại, Y khu vui chơi và Z nhà hàng sao cho tổng lợi nhuận là lớn nhất. Có tổng cộng N = X + Y + Z mảnh đất. Với mỗi mảnh đất i, ta có 3 lựa chọn tương ứng với 3 loại công trình và lợi nhuận tương ứng là Ai, Bi, C_i. Mỗi mảnh đất chỉ được xây dựng duy nhất một công trình. Bài toán này có thể được coi là một dạng bài phân chia tập hợp với ràng buộc số lượng.
Các cách tiếp cận
Cách Quy hoạch động
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int x, y, z, n;
struct Land {
int a, b, c;
} lands[MAXN];
int dp[MAXN][MAXN][MAXN];
int main() {
cin >> x >> y >> z;
n = x + y + z;
for(int i = 1; i <= n; ++i) {
cin >> lands[i].a >> lands[i].b >> lands[i].c;
}
// dp[i][j][k] là max profit khi xét i mảnh đất đầu tiên,
// đã xây dựng j TTTM và k Khu vui chơi.
// Nhà hàng sẽ là i - j - k.
memset(dp, -1, sizeof(dp));
dp[0][0][0] = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= min(i, x); ++j) {
for(int k = 0; k <= min(i - j, y); ++k) {
int l = i - j - k; // so nha hang
if (l > z) continue;
// Chon nha may
if (j > 0 && dp[i-1][j-1][k] != -1)
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k] + lands[i].a);
// Chon vui choi
if (k > 0 && dp[i-1][j][k-1] != -1)
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-1] + lands[i].b);
// Chon nha hang
if (l > 0 && dp[i-1][j][k] != -1)
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k] + lands[i].c);
}
}
}
cout << dp[n][x][y] << endl;
return 0;
}
- Time Complexity: O(N * X * Y)
- Space Complexity: O(X * Y)
Cách tiếp cận này sử dụng quy hoạch động 3 chiều. Trạng thái dp[i][j][k] lưu trữ lợi nhuận lớn nhất sau khi xét i mảnh đất, chọn j trung tâm thương mại và k khu vui chơi. Nhà hàng sẽ được xác định bởi số lượng còn lại. Tuy nhiên, do ràng buộc N <= 10^5, cách này chỉ hiệu quả với dữ liệu nhỏ (trong bài gốc N <= 100).
Cách Sử dụng Heap (Greedy)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, x, y, z;
struct Land {
int a, b, c;
// Sắp xếp theo hiệu số (a - b) giảm dần
bool operator<(const Land& other) {
return a - b > other.a - other.b;
}
} land[N];
long long pre[N], suf[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> x >> y >> z;
n = x + y + z;
for (int i = 1; i <= n; i++) {
cin >> land[i].a >> land[i].b >> land[i].c;
}
// Sap xep de chia thanh 2 phan: co kha nang chon A cao va chon B cao
sort(land + 1, land + 1 + n);
// Tinh tien su: tu dau den i, chon x thang co loi nhuan A lon nhat
// Co the hieu don gian la tinh mang pre[i]
// pre[i] = max profit tu 1..i neu chon x thang la A, con lai la C
priority_queue<int, vector<int>, greater<int>> pq;
ll sumC = 0, sumDiff = 0;
for (int i = 1; i <= n; i++) {
sumC += land[i].c;
pq.push(land[i].a - land[i].c);
sumDiff += land[i].a - land[i].c;
if ((int)pq.size() > x) {
sumDiff -= pq.top();
pq.pop();
}
if (i >= x) pre[i] = sumC + sumDiff;
}
// Tinh du su: tu cuoi den i, chon y thang co loi nhuan B lon nhat
// Day tuong tu nhu pre nhung di nguoc lai va chon Y
while(!pq.empty()) pq.pop();
sumC = 0; sumDiff = 0;
for (int i = n; i >= 1; i--) {
sumC += land[i].c;
pq.push(land[i].b - land[i].c);
sumDiff += land[i].b - land[i].c;
if ((int)pq.size() > y) {
sumDiff -= pq.top();
pq.pop();
}
if (i <= n - y + 1) suf[i] = sumC + sumDiff;
}
long long ans = 0;
for (int i = x; i <= n - y; i++) {
ans = max(ans, pre[i] + suf[i+1]);
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Bài toán có thể biến đổi thành: chọn X đất xây A, Y đất xây B, còn lại xây C. Nếu ta chia dãy thành 2 phần: phần đầu ưu tiên A, phần đuôi ưu tiên B. Hiệu số (A - B) giúp ta quyết định ranh giới.
- Sắp xếp các mảnh đất theo thứ tự giảm dần của (A - B).
- Chọn X đất xây A từ trái sang phải (sử dụng Min Heap để loại bỏ những đất có A-C nhỏ nhất nếu vượt quá X).
- Chọn Y đất xây B từ phải sang trái (tương tự).
- Duyệt qua các ranh giới để tìm giá trị lớn nhất của
pre[i] + suf[i+1].
Cách Lập trình hàm tối ưu (Dynamic Programming on Trees / Greedy)
// Approach 2 là cách tối ưu và phổ biến nhất trong các solution được cung cấp.
// Code dưới đây là phiên bản chi tiết của approach 2.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int X, Y, Z, n;
struct Land {
long long a, b, c;
// Sap xep giam dan theo (a - b)
bool operator<(const Land& other) const {
return a - b > other.a - other.b;
}
} L[N];
long long pre[N], suf[N];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
if (!(cin >> X >> Y >> Z)) return 0;
n = X + Y + Z;
for (int i = 1; i <= n; ++i) cin >> L[i].a >> L[i].b >> L[i].c;
sort(L + 1, L + 1 + n);
// Tinh pre[i]: tu 1..i, chon ra X thang de xay A, con lai xay C
// Bang cach su dung priority_queue de theo doi cac hieu so (A - C)
priority_queue<long long, vector<long long>, greater<long long>> pq;
long long sumAminusC = 0;
long long sumC = 0;
for (int i = 1; i <= n; ++i) {
sumC += L[i].c;
pq.push(L[i].a - L[i].c);
sumAminusC += L[i].a - L[i].c;
if (pq.size() > X) {
sumAminusC -= pq.top();
pq.pop();
}
if (i >= X) pre[i] = sumC + sumAminusC;
}
// Tinh suf[i]: tu i..n, chon ra Y thang de xay B, con lai xay C
while (!pq.empty()) pq.pop();
sumAminusC = 0; // Tai suy dung bien nay cho B - C
sumC = 0;
for (int i = n; i >= 1; --i) {
sumC += L[i].c;
pq.push(L[i].b - L[i].c);
sumAminusC += L[i].b - L[i].c;
if (pq.size() > Y) {
sumAminusC -= pq.top();
pq.pop();
}
if (i <= n - Y + 1) suf[i] = sumC + sumAminusC;
}
long long ans = 0;
for (int i = X; i <= n - Y; ++i) {
ans = max(ans, pre[i] + suf[i+1]);
}
cout << ans << endl;
return 0;
}
- Time Complexity: O(N log N)
- Space Complexity: O(N)
Đây là cách tiếp cận tối ưu.
- Sắp xếp: Sắp xếp các mảnh đất sao cho các mảnh đất có
A > B(hiệu số dương) nằm trước,B > Anằm sau. Điều này giúp chia dãy thành 2 phần rõ ràng. - Tiền xử lý (Prefix): Duyệt từ trái qua phải, duy trì một Min-Heap chứa các giá trị
A_i - C_i. Nếu số lượng chọn quá X, ta loại bỏ giá trị nhỏ nhất.pre[i]là tổng lợi nhuận tối đa từ mảnh 1 đến i nếu ta chỉ được chọn X đất xây A (và phần còn lại là C). - Hậu xử lý (Suffix): Tương tự, duyệt từ phải sang trái, duy trì Min-Heap chứa
B_i - C_i.suf[i]là tổng lợi nhuận tối đa từ i đến n nếu chỉ được chọn Y đất xây B. - Tìm kết quả: Duyệt qua tất cả các ranh giới
i(từ X đến n-Y), chia dãy thành [1...i] và [i+1...n]. Phần đầu sẽ tối ưu cho A, phần sau tối ưu cho B.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(N * X * Y) | O(X * Y) | Quy hoạch động |
| 2 | O(N log N) | O(N) | Sử dụng Heap (Greedy) |
| 3 | O(N log N) | O(N) | Lập trình hàm tối ưu (Dynamic Programming on Trees / Greedy) |
Bài học kinh nghiệm
- Bài toán có thể chia thành 2 giai đoạn: chọn X đất cho A (và phần còn lại cho C) và Y đất cho B (và phần còn lại cho C).
- Việc sắp xếp theo
(A - B)giảm dần là chìa khóa để xử lý mâu thuẫn giữa việc chọn A hay B. - Sử dụng Heap (Priority Queue) để quản lý top K phần tử lớn nhất là một kỹ thuật phổ biến để giải quyết các bài toán tối ưu có ràng buộc về số lượng.
Lỗi thường gặp
- Không xử lý đúng thứ tự duyệt trong bước tiền xử lý và hậu xử lý (một bên từ trái sang phải, một bên từ phải sang trái).
- Sử dụng quy hoạch động O(NXY) sẽ bị TLE do độ phức tạp quá cao với N lên tới 10^5.
- Lỗi truy cập mảng khi
i = ntrong vòng lặp tính suffix.
Bình luận