【HDU - 1069】 Monkey and Banana （基础dp）

佚名 4年前 (2020-02-26) 算法 550人围观抢沙发百度已收录

Monkey and Banana

直接写中文了

Problem Statement

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。一组研究人员正在设计一项实验，以测试猴子的智商。他们将挂香蕉在建筑物的屋顶，同时，提供一些砖块给这些猴子。如果猴子足够聪明，它应当能够通过合理的放置一些砖块建立一个塔，并爬上去吃他们最喜欢的香蕉。研究人员有n种类型的砖块，每种类型的砖块都有无限个。第i块砖块的长宽高分别用xi，yi，zi来表示。同时，由于砖块是可以旋转的，每个砖块的3条边可以组成6种不同的长宽高。在构建塔时，当且仅当A砖块的长和宽都分别小于B砖块的长和宽时，A砖块才能放到B砖块的上面，因为必须留有一些空间让猴子来踩。你的任务是编写一个程序，计算猴子们最高可以堆出的砖块们的高度。

Input

输入文件包含多组测试数据。每个测试用例的第一行包含一个整数n，代表不同种类的砖块数目。n<=30. 接下来n行，每行3个数，分别表示砖块的长宽高。当n= 0的时候，无需输出任何答案，测试结束。

Output

对于每组测试数据，输出最大高度。格式：Case 第几组数据: maximum height = 最大高度

Sample Input

1 10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0

Sample Output

Case 1: maximum height = 40 Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342

题目链接：

https://vjudge.net/problem/HDU-1069

一块砖头有6种方式去摆放（1,2,3）（1,3,2）（2,1,3）（2,3,1）（3,1,2）（3,2,1）

上面的砖头长（l），宽（s）必须分别小于下面的

dp[i]为第i个砖头是最下面的那个砖头时候可以达到的最大高度

AC代码

#include <bits/stdc++.h>
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x, y) memset(x, y, sizeof(x))
#define Maxn 1000
using namespace std;
struct node
{
    int l,s,h;//长 宽 高
    node(int l,int s,int h):l(l),s(s),h(h) {}
    bool operator<(const node &c)const//从小到大排序
    {
        if(l==c.l)
            return s<c.s;
        return l<c.l;
    }

};
vector<node> v;
int dp[Maxn];
int main()
{
    int n,k=0;
    while(cin>>n&&n!=0)
    {
        k++;
        v.clear();//清空，初始化
        MEM(dp,0);
        int cnt=0;
        int a,b,c;
        for(int i=0; i<n; i++)
        {
            cin>>a>>b>>c;//依次存入
            v.push_back(node(a,b,c));
            v.push_back(node(a,c,b));
            v.push_back(node(b,a,c));
            v.push_back(node(b,c,a));
            v.push_back(node(c,b,a));
            v.push_back(node(c,a,b));
        }
        sort(v.begin(),v.end());//排序
        int ans=0;
        for(int i=0; i<v.size(); i++)//从最小的那块砖开始
        {
            dp[i]=v[i].h;//一开始以就这一块砖头，dp[i]=v[i].h
            for(int j=i-1; j>=0; j--)//开始往上找比它小的砖头
            {
                //第j块砖头的长、宽分别比第i块小，且以第j块砖头为底层的高度+第i块砖的高度 大于 以第i块砖为底层的高度，则更新dp[i]
                if(v[j].l<v[i].l&&v[j].s<v[i].s&&dp[j]+v[i].h>dp[i])
                    dp[i]=dp[j]+v[i].h;
            }
            if(dp[i]>ans)
                ans=dp[i];
        }
        cout<<"Case "<<k<<": maximum height = "<<ans<<endl;
    }
    return 0;
}