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;
}
Trước hết ta cần sắp xếp cặp (l,r) theo r
Gọi dp[i] là tổng thời gian lớn nhất tại lượt thứ i
Như vậy ở trạng trái lượt thứ i ta sẽ có 2 lựa chọn:
+) Lựa chọn 1: Không chọn lượt thứ i thì có nghĩa là ta vẫn giữ nguyên thời gian lớn nhất của lượt thứ i-1 => time=dp[i-1]
+) Lựa chọn 2:Chọn lượt thứ i thì có nghĩa là ta cần tìm 1 lượt thứ j (j<i) mà khoảng (l,r) của lượt j không giao với khoảng (l,r) của i bằng cách tìm kiếm nhị phân.=> time=dp[j]+(r[i]-l[i]+1)
suy ra công thức truy hồi: dp[i]=max(dp[i-1],dp[j]+(r[i]-l[i]+1))
```cpp
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define __Hormer_Nguyen__ signed main()
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
const int MOD=1000000007;
const int maxn=5+1e5;
int n;
struct v
{
int l,r;
};
v a[maxn];
bool cmp(const v&x,const v&y)
{
return x.r<y.r;
}
int dp[maxn];
int tknp(int x)
{
int l=1;
int r=n;
int pos=-1;
while (l<=r)
{
int m=l+(r-l)/2;
if (a[m].r<x)
{
l=m+1;
pos=m;
}else
{
r=m-1;
}
}return pos;
}
__Hormer_Nguyen__
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
sort(a+1,a+n+1,cmp);
dp[1]=(a[1].r-a[1].l+1);
for (int i=2;i<=n;i++)
{
int k=tknp(a[i].l);
int val=(a[i].r-a[i].l+1);
dp[i]=max(dp[i-1],dp[k]+val);
}cout<<dp[n];
}
```
Sherwin
Created at
20 likes
Satyanshu111
Created at
9 likes