Hướng dẫn giải của [VTT Q4 Contest 13] Bài 4: Rô bốt [ROBOTS]
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ỗi rô bốt là một khoảng mở ~(x_i - L_i, x_i + L_i)~. Cần chọn nhiều khoảng nhất đôi một không chồng nhau; hai khoảng mở chỉ chạm đầu mút thì không chồng. Đây là bài chọn hoạt động kinh điển.
Sub 1: Vét cạn — ~O(2^n \cdot n^2)~, dùng khi ~n \le 20~
Duyệt mọi tập con, kiểm tra từng cặp trong tập có chồng nhau không (hai khoảng chồng khi ~\max(l_1, l_2) < \min(r_1, r_2)~), giữ tập hợp lệ lớn nhất. Nếu chỉ nộp sub này: đúng 4/20 test.
Sub 2: Quy hoạch động — ~O(n^2)~, dùng khi ~n \le 1000~
Sắp xếp theo đầu phải tăng dần. Gọi ~dp_i~ là số khoảng nhiều nhất chọn được mà khoảng cuối cùng là ~i~: ~dp_i = 1 + \max dp_j~ với mọi ~j~ trước đó có đầu phải ~\le~ đầu trái của ~i~. Đáp án là max các ~dp_i~. Nếu chỉ nộp sub này: đúng 11/20 test.
Sub 3: Tham lam — ~O(n \log n)~
Sắp xếp theo đầu phải tăng dần, duyệt lần lượt: nếu đầu trái của khoảng hiện tại ~\ge~ đầu phải của khoảng đã chọn cuối cùng thì chọn nó. Kết thúc sớm nhất thì để lại nhiều chỗ nhất cho các khoảng sau, nên cách này tối ưu. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu, ~n \le 20~ gọi sub1, ~n \le 1000~ gọi sub2, còn lại gọi sub3. 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;
long long L[100005], R[100005]; // khoảng mở (L, R)
// Sub 1: duyệt mọi tập con — O(2^n * n^2), dùng khi n <= 20
void sub1() {
int best = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int cnt = __builtin_popcount(mask);
if (cnt <= best) continue;
bool ok = true;
for (int i = 0; i < n && ok; i++) if (mask >> i & 1)
for (int j = i + 1; j < n; j++) if (mask >> j & 1)
if (max(L[i], L[j]) < min(R[i], R[j])) { ok = false; break; }
if (ok) best = cnt;
}
cout << best << "\n";
}
// Sub 2: sắp theo đầu phải, QHĐ dp[i] = 1 + max dp[j] với R[j] <= L[i] — O(n^2)
void sub2() {
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [](int x, int y) { return R[x] < R[y]; });
vector<int> dp(n, 1);
int best = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++)
if (R[id[j]] <= L[id[i]]) dp[i] = max(dp[i], dp[j] + 1);
best = max(best, dp[i]);
}
cout << best << "\n";
}
// Sub 3: tham lam — sắp theo đầu phải tăng dần, lấy khoảng nào bắt đầu >= đầu phải cuối cùng đã lấy
void sub3() {
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [](int x, int y) { return R[x] < R[y]; });
long long last = LLONG_MIN;
int cnt = 0;
for (int k = 0; k < n; k++) {
int i = id[k];
if (L[i] >= last) { cnt++; last = R[i]; }
}
cout << cnt << "\n";
}
int main() {
freopen("ROBOTS.INP", "r", stdin);
freopen("ROBOTS.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
long long x, l;
cin >> x >> l;
L[i] = x - l; R[i] = x + l;
}
if (n <= 20) sub1();
else if (n <= 1000) sub2();
else sub3();
}
Bình luận