Hướng dẫn giải của ROBOTS (THCS KS3 VTT)
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
Mỗi robot là một khoảng mở (x - L, x + L). Chọn nhiều nhất các khoảng không chồng lên nhau (ranh giới chạm được).
Sub 1: Quay lui, ~N \le 20~ ~O(2^N)~
Duyệt chọn/bỏ từng khoảng, kiểm tra không chồng. Không có test chấm nên chưa kiểm chứng.
Sub 2: Quy hoạch động, ~N \le 1000~ ~O(N^2)~
Sắp theo R, dp[i] = số khoảng lớn nhất kết thúc tại i.
Sub 3: Tham lam, ~N \le 10^5~ ~O(N \log N)~
Sắp theo R tăng dần, lấy khoảng nếu L >= R của khoảng vừa lấy.
Chương trình hoàn chỉnh
Nếu N <= 20 dùng sub 1, N <= 1000 dùng sub 2, còn lại dùng sub 3. Không có test chấm nên trạng thái là notest.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<pair<ll, ll>> iv; // khoang mo (L, R) cua moi robot
// Sub 1: quay lui, dung khi n <= 20: chon/bo tung khoang, kiem tra khong chong len nhau
int best1 = 0;
vector<pair<ll, ll>> chosen;
void bt(int i) {
if ((int)chosen.size() + (n - i) <= best1) return; // cat nhanh
if (i == n) {
best1 = max(best1, (int)chosen.size());
return;
}
bool ok = true;
for (auto& c : chosen)
if (!(iv[i].second <= c.first || c.second <= iv[i].first)) { ok = false; break; }
if (ok) {
chosen.push_back(iv[i]);
bt(i + 1);
chosen.pop_back();
}
bt(i + 1);
}
// Sub 2: quy hoach dong O(N^2), dung khi n <= 1000: sap theo R tang dan,
// dp[i] = so khoang lon nhat co khoang i la khoang cuoi cung
void sub2() {
sort(iv.begin(), iv.end(), [](const pair<ll, ll>& x, const pair<ll, ll>& y) { return x.second < y.second; });
vector<int> dp(n, 1);
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++)
if (iv[j].second <= iv[i].first) dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
cout << ans << "\n";
}
// Sub 3: tham lam O(N log N): sap theo R tang dan, lay khoang neu L >= R cua khoang vua lay
void sub3() {
sort(iv.begin(), iv.end(), [](const pair<ll, ll>& x, const pair<ll, ll>& y) { return x.second < y.second; });
ll last = LLONG_MIN;
int cnt = 0;
for (auto& p : iv) {
if (p.first >= last) {
cnt++;
last = p.second;
}
}
cout << cnt << "\n";
}
int main() {
cin >> n;
iv.resize(n);
for (int i = 0; i < n; i++) {
ll x, L;
cin >> x >> L;
iv[i] = {x - L, x + L};
}
if (n <= 20) {
bt(0);
cout << best1 << "\n";
} else if (n <= 1000) sub2();
else sub3();
return 0;
}
Bình luận