Register | Login

Solutions of Hall

Select solution language All Tiếng Việt English Other

Write solution here.

---

Sherwin    Created at    0 likes

Ta gọi dp[i] là thời gian sử dụng lớn nhất tính đến thời điểm i dp[0] = 0; Ta có công thức: dp[i] max(dp[i - 1], dp[j - 1] + i - j + 1) Dùng vector để lưu v[i] là tập hợp các phần tử kết thúc tại i ĐPT: O(n + max(A[i])) 1 <= i <= n Code mẫu: #include <bits/stdc++.h> using namespace std; int n; vector<int> v[100005]; int dp[100005]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1; i <= n; ++i){ int l, r; cin >> l >> r; v[r].push_back(l); } dp[0] = 0; for (int i = 1; i <= 100000; ++i){ dp[i] = dp[i-1]; for (int j : v[i]) dp[i] = max(dp[i], dp[j - 1] + i - j + 1); } cout << dp[100000]; }