题目链接 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; }

最新文章

  1. js三种方法添加image
  2. iOS 面试总结 二
  3. 为Xcode添加和备份快捷代码
  4. Spring中@Component注解,@Controller注解详解
  5. 各种浏览器css hack
  6. MongoDB牛刀小试
  7. 软件开发中的单一职责(转至INFOQ)
  8. C 栈实例
  9. win7如何开启和关闭超级管理员账户
  10. Linux学习——卸载Ubuntu,安装CentOS,第一次使用命令
  11. Bezier(贝塞尔)曲线简介
  12. MySQL基准测试(benchmark)
  13. 4日6日--ES5新增数组方法
  14. salesforce零基础学习(七十四)apex:actionRegion以及apex:actionSupport浅谈
  15. 关于怎么快速学好Android应用程序开发及其其他编程语言(大牛和高手勿喷,此篇文章也适合刚入门小师弟和小师妹)
  16. file按钮美化成图片(纯HTML+CSS)
  17. 比原链Bytom错误码一览
  18. multi-thread debug
  19. PHP的数据加密解密
  20. 推荐一个不错的关于Excel数据统计分析的公众号

热门文章

  1. Hive 分析函数lead、lag实例应用
  2. wap html5播放器和直播开发小结
  3. ogre3D学习基础3 -- 粒子与表层脚本
  4. Python3.0-3.6的版本变化
  5. python学习-- Django REST framework 序列化数据操作
  6. python学习-- Django Ajax CSRF 认证
  7. thinkphp3.2接入支付宝支付接口(PC端)
  8. Redis 配置登录密码
  9. windows通过NSF挂载centos目录
  10. 用jquery实现平滑的页面滚动效果