2018-2019賽季多校聯合新生訓練賽第第四場 H 搭積木
題目描述
積木對于大家來說應該很熟悉，我們可以用積木搭建出各種各樣的模型，不同的人搭建出來的模型也會不一樣。這不，小卡卡西正在和一群小伙伴玩積木呢！
鐵人老師看見小朋友們在玩積木，就給大家出了一個難題：給定一些方形的積木，積木的三維尺寸分別為正整數 Xi,Yi,Zi，每一種積木都可以認為是無限多個。并且在搭建程序中約定如下條件：
1. 搭建的模型每一層只能用一個積木；
2. 模型的每一層的積木的底面必須小于它的下層，當然積木的底面可以是6個面中的任一個。
那么要如何搭建，才能使模型最高呢？
輸入
第一行一個數 N，表示不同積木的種數（N<=1000）
以下 N行，每一行描述一種積木。
Xi、Yi、Zi(<=100)分別為三邊的長度
輸出
一行一個數 M，表示在給定的條件下能搭建的最高模型的高度。
樣例輸入
1
10 20 30
樣例輸出
40
uj5u.com熱心網友回復：
#include<bits/stdc++.h>using namespace std;
int n,i,j,f[3009];
struct stu{
int a;
int b;
int c;
}a[3009];
bool cmp(stu a,stu b){
return a.a<b.a;
}
int main()
{
cin>>n;
for(i=1;i<=n;i++){
cin>>a[i].a>>a[i].b>>a[i].c;
a[n+i].a=a[i].b;
a[n+i].b=a[i].c;
a[n+i].c=a[i].a;
a[2*n+i].a=a[i].c;
a[2*n+i].b=a[i].a;
a[2*n+i].c=a[i].b;
}
n=n*3;
for(i=1;i<=n;i++)
if(a[i].a>a[i].b)swap(a[i].a,a[i].b);
sort(a+1,a+1+n,cmp);
f[1]=a[1].c;
for(i=2;i<=n;i++){
f[i]=a[i].c;
for(j=1;j<=i-1;j++)
if(a[j].a<a[i].a&&a[j].b<a[i].b)
f[i]=max(f[i],f[j]+a[i].c);
}
cout<<f[n];
return 0;
}
uj5u.com熱心網友回復：
60分WA了uj5u.com熱心網友回復：
沒看懂哎，代碼中的資料3009怎么算出來的？uj5u.com熱心網友回復：
開大點總不會錯轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/15866.html
標籤：C++ 語言
上一篇：遇到奇怪現象，求大神解釋~~