本文共 1407 字，大约阅读时间需要 4 分钟。
排序b从小到大，在b相同排序a从小到大，使其满足如果i-1不能取，那么i-2也不能取，
这样从后往前推入栈，如果不满足推出栈直到满足再推入栈，每次推入的答案记录最大值即可。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 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_back17 #define mp make_pair18 #define all(x) (x).begin(),(x).end()19 #define fi first20 #define se second21 #define SZ(x) ((int)(x).size())22 typedef vector VI;23 typedef long long ll;24 typedef pair PII;25 const ll mod = 1000000007;26 const int inf = 0x3f3f3f3f;27 const double eps = 1e-7;28 // head29 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 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 }
转载于:https://www.cnblogs.com/baocong/p/6441536.html