ccbeginner

UVa Q437

Feb 6th, 2020
119
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q437
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define pii pair<int,int>
  5.  
  6. struct block{
  7.     pii area;
  8.     int h;
  9. }B[90];
  10.  
  11. bool cmp(const block &a, const block &b){
  12.     return a.area < b.area;
  13. }
  14.  
  15. int dp[90];
  16.  
  17. int main(){
  18.     int n,a,b,c, cnt = 0;
  19.     while(cin >> n){
  20.         if(n == 0)break;
  21.         for(int i = 0; i < n; ++i){
  22.             cin >> a >> b >> c;
  23.             B[i*3].area = (a < b)? make_pair(a,b) : make_pair(b,a);
  24.             B[i*3].h = c;
  25.             B[i*3+1].area = (b < c)? make_pair(b,c) : make_pair(c,b);
  26.             B[i*3+1].h = a;
  27.             B[i*3+2].area = (a < c)? make_pair(a,c) : make_pair(c,a);
  28.             B[i*3+2].h = b;
  29.         }
  30.         n *= 3;
  31.         sort(B, B+n, cmp);
  32.         for(int i = 0; i < n; ++i){
  33.             dp[i] = B[i].h;
  34.             for(int j = 0; j < i; ++j){
  35.                 if (B[i].area.first > B[j].area.first && B[i].area.second > B[j].area.second)
  36.                     dp[i] = max(dp[i], dp[j]+B[i].h);
  37.             }
  38.         }
  39.         int ans = 0;
  40.         for(int i = 0; i < n; ++i)ans = max(dp[i], ans);
  41.         cout << "Case " << ++cnt << ": maximum height = " << ans << '\n';
  42.     }
  43.     return 0;
  44. }
RAW Paste Data