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];
}
Let dp[i] = max time usage considering only 0....i bookings
base case:- dp[0] = (r[0]-l[0]+1) (it is good to accept if there is only one booking)
Transition :- dp[i] = max(dp[i-1], dp[j] + (r[i]-l[i]+1))
there are two cases possible either to take the booking or not
so dp[i-1] is when we not take the booking
dp[j] here j is the largest index which is not overlaping with current
so if we take it then we can take until j + current.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;
const ll INF = 1e18 + 7;
bool cmp(pair<int, int> a, pair<int, int> b)
{
return a.second < b.second;
}
void solve()
{
int n;
cin >> n;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i].first >> a[i].second;
}
sort(a.begin(), a.end(), cmp);
vector<int> dp(n);
dp[0] = a[0].second - a[0].first + 1;
for (int i = 1; i < n; i++)
{
dp[i] = dp[i - 1];
int l = 0, r = i - 1, j = -1;
while (l <= r)
{
int mid = (l + r) / 2;
int lj = a[mid].first;
int rj = a[mid].second;
if (rj < a[i].first)
{
j = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
int li = a[i].first;
int ri = a[i].second;
if (j != -1)
{
dp[i] = max(dp[i], dp[j] + (ri - li + 1));
}
else
{
dp[i] = max(dp[i], (ri - li + 1));
}
}
cout << dp[n - 1] << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while (t--)
{
solve();
}
return 0;
}
Sherwin
Created at
11 likes
Satyanshu111
Created at
4 likes