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

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

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

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

1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 100010 4 typedef long long LL; 5 struct node { 6 LL a, b, h; 7 } p[N]; 8 stack<node> sta; 9 10 bool cmp(const node &a, const node &b) { 11 if(a.b == b.b) return a.a < b.a; 12 return a.b > b.b; 13 } 14 15 int main() { 16 int n; 17 scanf("%d", &n); 18 for(int i = 1; i <= n; i++) scanf("%lld%lld%lld", &p[i].a, &p[i].b, &p[i].h); 19 sort(p + 1, p + 1 + n, cmp); 20 LL ans = p[1].h, cnt = p[1].h; 21 sta.push(p[1]); 22 for(int i = 2; i <= n; i++) { 23 if(sta.empty()) { 24 cnt += p[i].h; sta.push(p[i]); 25 continue; 26 } 27 node top = sta.top(); 28 if(top.a < p[i].b) { 29 cnt += p[i].h; 30 sta.push(p[i]); 31 } else { 32 ans = max(ans, cnt); 33 while(top.a >= p[i].b) { 34 cnt -= top.h; 35 sta.pop(); 36 if(sta.empty()) break; 37 top = sta.top(); 38 } 39 sta.push(p[i]); 40 cnt += p[i].h; 41 } 42 ans = max(ans, cnt); 43 } 44 printf("%lld\n", ans); 45 return 0; 46 }

 

转载于:https://www.cnblogs.com/fightfordream/p/6490157.html

总结

以上是生活随笔为你收集整理的Codeforces 777E：Hanoi Factory（贪心+栈）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。