Monkey and Banana
直接寫中文了
Problem Statement
一組研究人員正在設計一項實驗，以測驗猴子的智商，他們將掛香蕉在建筑物的屋頂，同時，提供一些磚塊給這些猴子，如果猴子足夠聰明，它應當能夠通過合理的放置一些磚塊建立一個塔，并爬上去吃他們最喜歡的香蕉， 研究人員有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; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83493.html
標籤：其他
上一篇：和為S的兩個數字