傻逼单调栈啊我怎么想了半天dp
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef struct P { LL a, b, h; P() {} P(LL a, LL b, LL h) : a(a), b(b), h(h) {} }P; const LL maxn = 100100; LL n; P p[maxn]; bool cmp(P x, P y) { if(x.b == y.b) return x.a > y.a; return x.b > y.b; } stack<P> st; signed main() { // freopen("in", "r", stdin); while(~scanf("%I64d", &n)) { for(LL i = 1; i <= n; i++) { scanf("%I64d%I64d%I64d",&p[i].a,&p[i].b,&p[i].h); } sort(p+1, p+n+1, cmp); while(!st.empty()) st.pop(); LL ret = 0; for(LL i = 1; i <= n; i++) { while(!st.empty() && p[i].b <= st.top().a) st.pop(); if(!st.empty()) p[i].h += st.top().h; st.push(p[i]); ret = max(ret, st.top().h); } printf("%I64d\n", ret); } return 0; }
转载于:https://www.cnblogs.com/zsben991126/p/11020597.html
