HDU-1069-Monkey and Banana-白红宇

HDU-1069-Monkey and Banana

阅读量：7015 次

发布时间：2019-06-28

本文共 1792 字，大约阅读时间需要 5 分钟。

链接：https://vjudge.net/problem/HDU-1069#author=prayerhgq

题意：

一组研究人员正在设计一项实验，以测试猴子的智商。他们将挂香蕉在建筑物的屋顶，同时，提供一些砖块给这些猴子。如果猴子足够聪明，它应当能够通过合理的放置一些砖块建立一个塔，并爬上去吃他们最喜欢的香蕉。

研究人员有n种类型的砖块，每种类型的砖块都有无限个。第i块砖块的长宽高分别用xi，yi，zi来表示。同时，由于砖块是可以旋转的，每个砖块的3条边可以组成6种不同的长宽高。

在构建塔时，当且仅当A砖块的长和宽都分别小于B砖块的长和宽时，A砖块才能放到B砖块的上面，因为必须留有一些空间让猴子来踩。

你的任务是编写一个程序，计算猴子们最高可以堆出的砖块们的高度。

思路：

结构体记录每三个数可以形成的砖块，以长宽排序，从小到大遍历，将每个砖块上面能垒上去的高度叠加。

因为从小往大，之前的砖块都是能垒的最大高度。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 using namespace std;typedef long long LL;const int MAXN = 30 * 6 + 10;const int INF = 0x7fffffff;struct Node{ int _x, _y; int _h; bool operator < (const Node & that) const { if (this->_x != that._x) return this->_x < that._x; return this->_y < that._y; }}node[MAXN];int main(){ int n; int a, b, c; int cnt = 1; while (cin >> n && n) { int pos = 0; for (int i = 1;i <= n;i++) { cin >> a >> b >> c; pos++, node[pos]._x = a, node[pos]._y = b, node[pos]._h = c; pos++, node[pos]._x = a, node[pos]._y = c, node[pos]._h = b; pos++, node[pos]._x = b, node[pos]._y = a, node[pos]._h = c; pos++, node[pos]._x = b, node[pos]._y = c, node[pos]._h = a; pos++, node[pos]._x = c, node[pos]._y = a, node[pos]._h = b; pos++, node[pos]._x = c, node[pos]._y = b, node[pos]._h = a; } sort(node + 1, node + 1 + pos); int res = node[1]._h; for (int i = 1;i <= pos;i++) { int tmp = 0; for (int j = 1;j < i;j++) { if (node[j]._x < node[i]._x && node[j]._y < node[i]._y) tmp = max(tmp, node[j]._h); } node[i]._h += tmp; res = max(res, node[i]._h); } printf("Case %d: maximum height = %d\n", cnt++, res); } return 0;}

转载于:https://www.cnblogs.com/YDDDD/p/10354927.html

你可能感兴趣的文章