Problem - 1069

　　隨便找到的一道題目。

　　題意是給出一些的長方體，長方體可以用任意次數，可以任意翻轉。如果一個長方體可以疊在另一個長方體上，條件是這個長方體的長和寬嚴格小于另一個長方體的長和寬。問給出的n種長方體最高可以疊到多高。

　　因為長方體有三種不同的面，而且長方體的長和寬要嚴格小于前一個，所以可以將一個長方體拆成三種不同的面作為底面的長方體，而且假設長總是大于寬的。將長方體按照長和寬排序，然后假設len[i]是放置第i個長方體的時候能得到的最大高度，之后的做法基本上跟LIS的操作一樣了。

　代碼如下：

1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 5 using namespace std; 6 7 struct Node { 8 int l[3]; 9 } rec[111]; 10 11 bool cmp(Node a, Node b) { 12 if (a.l[1] != b.l[1]) return a.l[1] < b.l[1]; 13 return a.l[2] < b.l[2]; 14 } 15 16 int len[111]; 17 18 int main() { 19 // freopen("in", "r", stdin); 20 int n, cas = 1; 21 while (cin >> n && n) { 22 for (int i = 0; i < n; i++) { 23 for (int j = 0; j < 3; j++) { 24 cin >> rec[i * 3].l[j]; 25 } 26 sort(rec[i * 3].l, rec[i * 3].l + 3); 27 for (int j = 1; j <= 2; j++) { 28 rec[i * 3 + j] = rec[i * 3]; 29 swap(rec[i * 3 + j].l[0], rec[i * 3 + j].l[1]); 30 } 31 swap(rec[i * 3 + 2].l[0], rec[i * 3 + 2].l[2]); 32 } 33 n *= 3; 34 int mx = 0; 35 sort(rec, rec + n, cmp); 36 for (int i = 0; i < n; i++) { 37 len[i] = 0; 38 for (int j = 0; j < i; j++) { 39 if (rec[j].l[1] < rec[i].l[1] && rec[j].l[2] < rec[i].l[2]) { 40 len[i] = max(len[j], len[i]); 41 } 42 } 43 len[i] += rec[i].l[0]; 44 mx = max(mx, len[i]); 45 } 46 printf("Case %d: maximum height = %d\n", cas++, mx); 47 } 48 return 0; 49 } View Code

?

——written by Lyon

轉載于:https://www.cnblogs.com/LyonLys/archive/2013/05/25/hdu_1069_Lyon.html

總結

以上是生活随笔為你收集整理的hdu 1069 Monkey and Banana （LIS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。