1 条题解
-
0
#include <bits/stdc++.h> #define int long long using namespace std; const int MAXN = 100000; int n; struct Line { int l, r, v; }; Line a[MAXN + 5]; vector<int> temp; // 离散化 bool cmp(Line a, Line b) { return a.r < b.r; } // dp[i]:1~i 这个范围内能得到的最大快乐度 int dp[MAXN * 2 + 5]; // s[i] 记录右端点为 i 的所有区间编号 vector<int> s[MAXN * 2 + 5]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r >> a[i].v; // 离散化 for (int i = 1; i <= n; i++) { temp.push_back(a[i].l); temp.push_back(a[i].r); } sort(temp.begin(), temp.end()); for (int i = 1; i <= n; i++) { // 坐标对应到 1~2n(因为前面没去重,所以中间可能有缺的位置) a[i].l = lower_bound(temp.begin(), temp.end(), a[i].l) - temp.begin() + 1; a[i].r = lower_bound(temp.begin(), temp.end(), a[i].r) - temp.begin() + 1; } // 把每个区间存入对应右端点中 sort(a + 1, a + n + 1, cmp); for (int i = 1; i <= n; i++) s[a[i].r].push_back(i); // dp for (int i = 1; i <= 2 * n; i++) { dp[i] = dp[i - 1]; // 先继承 1~i-1 的最大快乐值 // 检查所有右端点在 i 的区间 // 如果使用了第 j 个区间,那么带来了 a[j].v 的快乐值,然后第 j 个区间范围内就不能用了 for (int &j : s[i]) dp[i] = max(dp[i], dp[a[j].l - 1] + a[j].v); } cout << dp[2 * n]; return 0; }
- 1
信息
- ID
- 1794
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- (无)
- 递交数
- 36
- 已通过
- 14
- 上传者