Codeforces 777E：Hanoi Factory（贪心+栈）

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

题意：给出n个环状圆柱，每个圆环有一个内半径a，外半径b，和高度h，只有外半径bj <= bi并且bj > ai，这样j才可以放在i的上面，问最大能达到的高度是多少。

思路：一开始用数组dp错了，主要是推错转移方程。用不到之前的信息了。如果要利用之前的信息，其实是可以用栈来维护的。先按照外半径从大到小，外半径相同内半径从大到小排序，这样能保证如果前面符合，后面放上去能使高度最大。

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 typedef long long LL;

 struct node {

     LL a, b, h;

 } p[N];

 stack<node> sta;

 bool cmp(const node &a, const node &b) {

     if(a.b == b.b) return a.a < b.a;

     return a.b > b.b;

 }

 int main() {

     int n;

     scanf("%d", &n);

     for(int i = ; i <= n; i++) scanf("%lld%lld%lld", &p[i].a, &p[i].b, &p[i].h);

     sort(p + , p +  + n, cmp);

     LL ans = p[].h, cnt = p[].h;

     sta.push(p[]);

     for(int i = ; i <= n; i++) {

         if(sta.empty()) {

             cnt += p[i].h; sta.push(p[i]);

             continue;

         }

         node top = sta.top();

         if(top.a < p[i].b) {

             cnt += p[i].h;

             sta.push(p[i]);

         } else {

             ans = max(ans, cnt);

             while(top.a >= p[i].b) {

                 cnt -= top.h;

                 sta.pop();

                 if(sta.empty()) break;

                 top = sta.top();

             }

             sta.push(p[i]);

             cnt += p[i].h;

         }

         ans = max(ans, cnt);

     }

     printf("%lld\n", ans);

     return ;

 }