C&C++   发布时间:2022-04-03  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了普及C组第二题大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。

2000. 【2015.8.6普及组模拟赛】Leo搭积木(brick) 

 题目:

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

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


输入:

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

输出

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

样例输入

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

 

样例输出

Sample Output1:
40


Sample Output2:
21


Sample Output3:
342

数据范围限制

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

思路:(师出此人)

本人动态规划不咋行,所以问了一下师兄,他给我做了番解释,可能讲的不太好,看不明白请移步至他的博客

首先虑下长宽高的组合情况——设长宽高,x,y,z。则有六种排列组合。但是由于场必须大于宽,所以减少了一半为三种。

读题很容易知道这是线性DP中的最长单调下降序列。典型的模板题(便我还是不会做)我们用结构体去赋值,然后我们可以将长宽分别排成两种序列。之后就是动态规划。然后就能得出答案。

CODE

#include<cstdio>
#include<iostream>
#include<cString>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a1,b1,c1,hh=1,p[9001],ans=0;
struct jimu{
    int a,b,c;
};
jimu q[9001];
bool mnp1(jimu x,jimu y)
{
    return x.b>y.b;
}
bool mnp2(jimu x,jimu y)
{
    return x.c>y.c;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a1>>b1>>c1;
        q[3*i-2].c=@H_853_116@min(a1,b1);
        q[3*i-1].c=@H_853_116@min(a1,c1);
        q[3*i].c=@H_853_116@min(b1,c1);
        q[3*i-2].b=@H_853_116@max(a1,b1);
        q[3*i-1].b=@H_853_116@max(a1,c1);
        q[3*i].b=@H_853_116@max(c1,b1);
        q[3*i-2].a=a1;
        q[3*i-1].a=b1;
        q[3*i].a=c1;
    }
    sort(q+1,q+3*n+1,mnp1);
    for(int i=1;i<=3*n;i++)
    {
        if(q[i].b!=q[i-1].b)
        {
            sort(q+hh,q+i,mnp2);
            hh=i;
        }
    }
    for(int i=1;i<=3*n;i++)
    p[i]=q[i].a;
    for(int i=1;i<=3*n;i++)
    {
        for(int j=i-1;j>=1;j--)
        {
            if(p[j]+q[i].a>=p[i]&&q[j].b>q[i].b&&q[j].c>q[i].C)
            p[i]=p[j]+q[i].a;
        }
    }
    for(int i=1;i<=3*n;i++)
    {
        if(p[i]>=ans)
        ans=p[i];
    }
    cout<<ans;
    return 0;
}

感谢大佬给我的讲解,我将永远铭记他。

完结撒花。

我的代码也是仿照他的写的,嘿嘿

                                                                                                                                                                                                   

大佬总结

以上是大佬教程为你收集整理的普及C组第二题全部内容,希望文章能够帮你解决普及C组第二题所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。