Dang_Quan_10_Tin

TOWER TS10 PTNK 2012-2013

Jan 15th, 2022
631
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define task "TOWER"
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using ld = long double;
  11.  
  12. constexpr int N = 1e2 + 5;
  13. int n, f[N];
  14. struct KhoiDa
  15. {
  16.     int a, b, g;
  17.     bool operator<(const KhoiDa &x) const
  18.     {
  19.         return a > x.a || (a == x.a && b > x.b);
  20.     }
  21. } s[N];
  22.  
  23. void Read()
  24. {
  25.     cin >> n;
  26.  
  27.     for (int i = 1; i <= n; ++i)
  28.     {
  29.         cin >> s[i].a >> s[i].b >> s[i].g;
  30.         if (s[i].a > s[i].b)
  31.             swap(s[i].a, s[i].b);
  32.     }
  33. }
  34.  
  35. void Solve()
  36. {
  37.     sort(s + 1, s + n + 1);
  38.     // Sắp xếp các khối đá theo chiều giảm của chiều rộng và chiều dài để vừa duyệt từ đầu đến cuối và vừa tính toán hàm mục tiêu
  39.  
  40.     for (int i = 1; i <= n; ++i)
  41.     {
  42.         f[i] = s[i].g;
  43.         for (int j = 1; j < i; ++j)
  44.             if (s[i].a <= s[j].a && s[i].b <= s[j].b)
  45.                 f[i] = max(f[i], f[j] + s[i].g);
  46.     }
  47.  
  48.     cout << *max_element(f + 1, f + n + 1);
  49. }
  50.  
  51. int32_t main()
  52. {
  53.     ios::sync_with_stdio(0);
  54.     cin.tie(0);
  55.     cout.tie(0);
  56.     if (fopen(task ".INP", "r"))
  57.     {
  58.         freopen(task ".INP", "r", stdin);
  59.         freopen(task ".OUT", "w", stdout);
  60.     }
  61.  
  62.     Read();
  63.     Solve();
  64. }
  65.  
RAW Paste Data