Codeforces 777E Hanoi Factory(线段树维护DP)
2024-10-20 07:47:25
题目链接 Hanoi Factory
很容易想到这是一个DAG模型,那么状态转移方程就出来了。
但是排序的时候有个小细节:b相同时看a的值。
因为按照惯例,堆塔的时候肯定是内半径大的在下面。
因为N有1e5,那么DP的时候用线段树优化一下,就可以了。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i(a); i <= (b); ++i) typedef long long LL; const int N = 200000 + 10; struct Segtree{
int l, r;
LL num;
} segtree[N << 2]; struct node{
int a, b;
LL h;
friend bool operator < (const node &A, const node &B){
return A.b == B.b ? A.a > B.a : A.b > B.b;
}
} c[N]; struct Node{
int x, y;
friend bool operator < (const Node &a, const Node &b){
return a.x < b.x;
}
} f[N]; int aa[N], bb[N];
int n, m, cnt;
map <int, int> mp;
LL ans; inline void pushup(int i){
segtree[i].num = max(segtree[i << 1].num, segtree[i << 1 | 1].num);
} void build(int i, int l, int r){ segtree[i].l = l;
segtree[i].r = r;
segtree[i].num = 0; if (l == r) return ;
int mid = (l + r) >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
} void update(int i, int pos, LL value){
int L = segtree[i].l, R = segtree[i].r;
if (L == R && L == pos){
segtree[i].num = max(segtree[i].num, value);
return;
} int mid = L + R >> 1;
if (pos <= mid) update(i << 1, pos, value);
else update(i << 1 | 1, pos, value); pushup(i);
} LL query(int i, int l, int r){
int L = segtree[i].l, R = segtree[i].r;
if (L == l && R == r) return segtree[i].num;
int mid = L + R >> 1;
LL ret = 0;
if (r <= mid)
ret = max(ret, query(i << 1, l, r));
else
if (l > mid)
ret = max(ret, query(i << 1 | 1, l, r));
else
{
ret = max(ret, query(i << 1, l, mid));
ret = max(ret, query(i << 1 | 1, mid + 1, r));
} return ret;
} int main(){ scanf("%d", &n);
cnt = 0;
rep(i, 1, n){
scanf("%d%d%lld", aa + i, bb + i, &c[i].h);
f[++cnt].x = aa[i];
f[++cnt].x = bb[i];
} sort(f + 1, f + cnt + 1); f[1].y = 1;
rep(i, 2, cnt) f[i].y = f[i].x == f[i - 1].x ? f[i - 1].y : f[i - 1].y + 1;
rep(i, 1, cnt) mp[f[i].x] = f[i].y; rep(i, 1, n){
c[i].a = mp[aa[i]];
c[i].b = mp[bb[i]];
} sort(c + 1, c + n + 1); m = 0;
rep(i, 1, n){
m = max(m, c[i].a);
m = max(m, c[i].b);
} build(1, 1, m); rep(i, 1, n){
LL now = query(1, 1, c[i].b - 1);
LL cnt = now + c[i].h;
ans = max(ans, cnt);
update(1, c[i].a, cnt);
} printf("%lld\n", ans); return 0; }
最新文章
- js三种方法添加image
- iOS 面试总结 二
- 为Xcode添加和备份快捷代码
- Spring中@Component注解,@Controller注解详解
- 各种浏览器css hack
- MongoDB牛刀小试
- 软件开发中的单一职责(转至INFOQ)
- C 栈实例
- win7如何开启和关闭超级管理员账户
- Linux学习——卸载Ubuntu,安装CentOS,第一次使用命令
- Bezier(贝塞尔)曲线简介
- MySQL基准测试(benchmark)
- 4日6日--ES5新增数组方法
- salesforce零基础学习(七十四)apex:actionRegion以及apex:actionSupport浅谈
- 关于怎么快速学好Android应用程序开发及其其他编程语言(大牛和高手勿喷,此篇文章也适合刚入门小师弟和小师妹)
- file按钮美化成图片(纯HTML+CSS)
- 比原链Bytom错误码一览
- multi-thread debug
- PHP的数据加密解密
- 推荐一个不错的关于Excel数据统计分析的公众号