首页 > 代码库 > Codeforces 777D Hanoi Factory(线段树维护DP)
Codeforces 777D Hanoi Factory(线段树维护DP)
题目链接 Hanoi Factory
很容易想到这是一个DAG模型,那么状态转移方程就出来了。
但是排序的时候有个小细节:b相同时看a的值。
因为按照惯例,堆塔的时候肯定是内半径大的在下面。
因为N有1e5,那么DP的时候用线段树优化一下,就可以了。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define rep(i, a, b) for(int i(a); i <= (b); ++i) 6 7 typedef long long LL; 8 9 const int N = 200000 + 10; 10 11 struct Segtree{ 12 int l, r; 13 LL num; 14 } segtree[N << 2]; 15 16 struct node{ 17 int a, b; 18 LL h; 19 friend bool operator < (const node &A, const node &B){ 20 return A.b == B.b ? A.a > B.a : A.b > B.b; 21 } 22 } c[N]; 23 24 struct Node{ 25 int x, y; 26 friend bool operator < (const Node &a, const Node &b){ 27 return a.x < b.x; 28 } 29 } f[N]; 30 31 int aa[N], bb[N]; 32 int n, m, cnt; 33 map <int, int> mp; 34 LL ans; 35 36 inline void pushup(int i){ 37 segtree[i].num = max(segtree[i << 1].num, segtree[i << 1 | 1].num); 38 } 39 40 void build(int i, int l, int r){ 41 42 segtree[i].l = l; 43 segtree[i].r = r; 44 segtree[i].num = 0; 45 46 if (l == r) return ; 47 int mid = (l + r) >> 1; 48 build(i << 1, l, mid); 49 build(i << 1 | 1, mid + 1, r); 50 } 51 52 void update(int i, int pos, LL value){ 53 int L = segtree[i].l, R = segtree[i].r; 54 if (L == R && L == pos){ 55 segtree[i].num = max(segtree[i].num, value); 56 return; 57 } 58 59 int mid = L + R >> 1; 60 if (pos <= mid) update(i << 1, pos, value); 61 else update(i << 1 | 1, pos, value); 62 63 pushup(i); 64 } 65 66 67 LL query(int i, int l, int r){ 68 int L = segtree[i].l, R = segtree[i].r; 69 if (L == l && R == r) return segtree[i].num; 70 int mid = L + R >> 1; 71 LL ret = 0; 72 if (r <= mid) 73 ret = max(ret, query(i << 1, l, r)); 74 else 75 if (l > mid) 76 ret = max(ret, query(i << 1 | 1, l, r)); 77 else 78 { 79 ret = max(ret, query(i << 1, l, mid)); 80 ret = max(ret, query(i << 1 | 1, mid + 1, r)); 81 } 82 83 return ret; 84 } 85 86 87 int main(){ 88 89 scanf("%d", &n); 90 cnt = 0; 91 rep(i, 1, n){ 92 scanf("%d%d%lld", aa + i, bb + i, &c[i].h); 93 f[++cnt].x = aa[i]; 94 f[++cnt].x = bb[i]; 95 } 96 97 sort(f + 1, f + cnt + 1); 98 99 f[1].y = 1; 100 rep(i, 2, cnt) f[i].y = f[i].x == f[i - 1].x ? f[i - 1].y : f[i - 1].y + 1; 101 rep(i, 1, cnt) mp[f[i].x] = f[i].y; 102 103 rep(i, 1, n){ 104 c[i].a = mp[aa[i]]; 105 c[i].b = mp[bb[i]]; 106 } 107 108 sort(c + 1, c + n + 1); 109 110 m = 0; 111 rep(i, 1, n){ 112 m = max(m, c[i].a); 113 m = max(m, c[i].b); 114 } 115 116 build(1, 1, m); 117 118 rep(i, 1, n){ 119 LL now = query(1, 1, c[i].b - 1); 120 LL cnt = now + c[i].h; 121 ans = max(ans, cnt); 122 update(1, c[i].a, cnt); 123 } 124 125 printf("%lld\n", ans); 126 127 return 0; 128 129 }
Codeforces 777D Hanoi Factory(线段树维护DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。