input:brick.in output:brick.out

时间限制: 1000 ms 空间限制: 128000 KB

题目描述

​ Leo是一个快乐的火星人，总是能和地球上的OIers玩得很high。
​ 2012到了，Leo又被召回火星了，在火星上没人陪他玩了，但是他有好多好多积木，于是他开始搭积木玩。
​ 火星人能制造n种积木，积木能无限供应。每种积木都是长方体，第i种积木的长、宽、高分别为li、wi、hi。积木可以旋转，使得长宽高任意变换。Leo想要用这些积木搭一个最高的塔。问题是，如果要把一个积木放在另一个积木上面，必须保证上面积木的长和宽都严格小于下面积木的长和宽。这意味着，即使两块长宽相同的积木也不能堆起来。
​ 火星上没有电脑，好心的你决定帮助Leo求出最高的塔的高度。

【提示】
每种积木都可以拆分成高度分别为li、wi、hi的三种积木，另两边作为长和宽，保证长>=宽。

输入

第一行，一个整数n，表示积木的种数
接下来n行，每行3个整数li，wi，hi，表示积木的长宽高

输出

一行一个整数，表示塔高的最大值

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Sample Input1:
1
10 20 30

Sample Input2:
2
6 8 10
5 5 5
Sample Input3:
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27

样例输出

1
2
3
4
5
6
7
8
Sample Output1:
40

Sample Output2:
21

Sample Output3:
342

数据范围限制

对于30%的数据 n<=8
对于100%的数据 n<=3000,最后答案不会超过32位整型

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
struct Node{
    int w,l,h;
}a[10001];
bool bdx(Node c,Node d)
{
    return c.l<d.l;
}
int main()
{
    freopen("brick.in","r",stdin);
    freopen("brick.out","w",stdout);
    int n,f[10001],ans;
    cin>>n;
    int o,p,q;
    for(int i=1;i<=n;i++)
    {
        cin>>o>>p>>q;
        a[i].l=max(o,p);a[i].w=min(o,p);a[i].h=q;
        a[i+n].l=max(o,q);a[i+n].w=min(o,q);a[i+n].h=p;
        a[i+2*n].l=max(p,q);a[i+2*n].w=min(p,q);a[i+2*n].h=o;
    }
    sort(a+1,a+3*n+1,bdx);
    for(int i=1;i<=3*n;i++)
        f[i]=a[i].h;
    for(register int i=3*n;i>=1;i--)
        for(register int j=i+1;j<=3*n;j++)
            if(a[i].w<a[j].w && a[i].l != a[j].l)
                f[i]=max(f[j]+a[i].h,f[i]);
    for(int i=1;i<=3*n;i++)
    ans=max(ans,f[i]);
    cout<<ans;
}