传送门：https://codeforces.com/problemset/problem/777/E
E. Hanoi Factory
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Egypt ordered the workers of Hanoi Factory to create as high tower as possible. They were not ready to serve such a strange order so they had to create this new tower using already produced rings.
There are n rings in factory's stock. The i-th ring has inner radius ai, outer radius bi and height hi. The goal is to select some subset of rings and arrange them such that the following conditions are satisfied:
- Outer radiuses form a non-increasing sequence, i.e. one can put the j-th ring on the i-th ring only if bj?≤?bi.
- Rings should not fall one into the the other. That means one can place ring j on the ring i only if bj?>?ai.
- The total height of all rings used should be maximum possible.
Input
The first line of the input contains a single integer n (1?≤?n?≤?100?000) — the number of rings in factory's stock.
The i-th of the next n lines contains three integers ai, bi and hi (1?≤?ai,?bi,?hi?≤?109, bi?>?ai) — inner radius, outer radius and the height of the i-th ring respectively.
Output
Print one integer — the maximum height of the tower that can be obtained.
Examples
input
Copy
3
1 5 1
2 6 2
3 7 3
output
Copy
6
input
Copy
4
1 2 1
1 3 3
4 6 2
5 7 1
output
Copy
4
Note
In the first sample, the optimal solution is to take all the rings and put them on each other in order 3, 2, 1.
In the second sample, one can put the ring 3 on the ring 4 and get the tower of height 3, or put the ring 1 on the ring 2 and get the tower of height 4.
会给你n个圆环，并且告知他们的内环半径和外环半径，以及他们的高，问你怎么摆放可以使得高度最高
摆放的要求如下: 如果讲j放在i上，那么要保证a[i] < b[j] && b[j] <= a[i]
第一想法可以直接排序，按b从大到小排序，当b相同的时候，就按a从大到小排序（因为可以观察到，b从大到小很容易可以得知，当b相同的时候，由于a[i] < b[j]这个条件，我们可以从大到小排序，可以知道，如果当前i的a是小于j的b才可以放在i上面），然后现在得到了一个近乎单调性的数组，接着用一个单调栈然后，每次入栈，判断栈顶和当前i的大小关系，是否不满足，不满足的话就出栈，出到满足位置（如果都不满足当前的i的话，那栈内的更不可能满足i + 1到n的圆盘，根据单调性可以得知），并且对于每次ans取个max即可，一A
后面看tags也有dp的tag，但是目前还没不会dp的做法。。。（dp完全不会呜呜）
代码如下：
#include <bits/stdc++.h>
#include <time.h>
#define first fi
#define second seusing namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmpp(db a,db b){ return sign(a - b);}
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = x / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}
ll c,n,k;
struct node{int a,b,h;
}g[maxn];
bool cmp(node a,node b){if(a.b == b.b) return a.a > b.a;return a.b > b.b;
}
int main() {ios::sync_with_stdio(false);while(cin >> n){stack<node>s;for(int i = 1;i <= n;i++) cin >> g[i].a >> g[i].b >> g[i].h ;sort(g + 1, g + 1 + n,cmp);ll ans = 0,num = 0;for(int i = 1;i <= n;i++){
// cout << g[i].a << " " << g[i].b << " " << g[i].h << endl;}for(int i = 1;i <= n;i++){if(!s.empty()){while(!s.empty() && (g[i].b <= s.top().a || g[i].b > s.top().b)){num -= s.top().h;s.pop();}s.push(g[i]);num += g[i].h;ans = max(ans,(long long)num);}else s.push(g[i]),num += g[i].h,ans = max(ans,num);
// cout << num << endl;}cout << ans << endl;}//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}