[CF777E] Hanoi Factory - 线段树优化dp
Description
给你n个环,每个环有内径a,外径b,高度v,现在让你将这n个环重起来,问你能重的最大高度。 满足条件:bi>=bj,bj>ai。(i<j)
Solution
首先想到按 b 降序排序,注意在 b 相同时要按 a 降序排序
然后就是类似背包的简单 dp,线段树优化即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int val[N];
void modify(int p, int l, int r, int pos, int key)
{
val[p] = max(val[p], key);
if (l < r)
{
if (pos <= (l + r) / 2)
modify(p * 2, l, (l + r) / 2, pos, key);
else
modify(p * 2 + 1, (l + r) / 2 + 1, r, pos, key);
}
}
int query(int p, int l, int r, int ql, int qr)
{
if (l > qr || r < ql)
return 0;
if (l >= ql && r <= qr)
return val[p];
return max(query(p * 2, l, (l + r) / 2, ql, qr), query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr));
}
int n;
struct Node
{
int a, b, h;
bool operator<(const Node &rhs) const
{
if (b == rhs.b)
return a > rhs.a;
else
return b > rhs.b;
}
} node[N];
signed main()
{
ios::sync_with_stdio(false);
cin >> n;
map<int, int> mp;
for (int i = 1; i <= n; i++)
{
cin >> node[i].a >> node[i].b >> node[i].h;
mp[node[i].a]++;
mp[node[i].b - 1]++;
}
int ind = 0;
for (auto &[x, y] : mp)
y = ++ind;
sort(node + 1, node + n + 1);
for (int i = 1; i <= n; i++)
{
int mx = query(1, 1, ind, 1, mp[node[i].b - 1]);
modify(1, 1, ind, mp[node[i].a], mx + node[i].h);
}
cout << query(1, 1, ind, 1, ind) << endl;
}