首页 > 代码库 > 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)