Codeforces Round #401 (Div. 2) E. Hanoi Factory 栈

E. Hanoi Factory

链接：

http://codeforces.com/contest/777/problem/E

题解：

排序b从小到大，在b相同排序a从小到大，使其满足如果i-1不能取，那么i-2也不能取，

这样从后往前推入栈，如果不满足推出栈直到满足再推入栈，每次推入的答案记录最大值即可。

代码：

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <queue>
 5 #include <stack>
 6 #include <cstdio>
 7 #include <string>
 8 #include <vector>
 9 #include <cstring>
10 #include <iostream>
11 #include <algorithm>
12 #include <functional>
13 using namespace std;
14 #define rep(i,a,n) for (int i=a;i<=n;i++)
15 #define per(i,a,n) for (int i=n;i>=a;i--)
16 #define pb push_back
17 #define mp make_pair
18 #define all(x) (x).begin(),(x).end()
19 #define fi first
20 #define se second
21 #define SZ(x) ((int)(x).size())
22 typedef vector<int> VI;
23 typedef long long ll;
24 typedef pair<int, int> PII;
25 const ll mod = 1000000007;
26 const int inf = 0x3f3f3f3f;
27 const double eps = 1e-7;
28 // head
29 
30 const int maxn = 1e5 + 7;
31 
32 struct Ring {
33     int a, b;
34     ll h;
35     bool operator < (Ring r) {
36         if (b == r.b) return a < r.a;
37         return b < r.b;
38     }
39 }r[maxn];
40 
41 int main() {
42     int n;
43     cin >> n;
44     rep(i, 1, n) cin >> r[i].a >> r[i].b >> r[i].h;
45     sort(r + 1, r + 1 + n);
46     stack<Ring> ms;
47     ll ans = 0, sum = 0;
48     per(i, 1, n) {
49         while (1) {
50             if (ms.empty()) break;
51             if (ms.top().b >= r[i].b && ms.top().a < r[i].b) break;
52             sum -= ms.top().h;
53             ms.pop();
54         }
55         ms.push(r[i]);
56         sum += r[i].h;
57         ans = max(ans, sum);
58     }
59     cout << ans << endl;
60     return 0;
61 }