Monkey and Banana（线性dp）

AC_Code:
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn = 222;
 8 
 9 int n,ans[maxn];
10 struct node{
11     int len,wide,high;
12 }block[maxn];
13 
14 bool cmp(node a, node b){//长从小到大排,长相同时,款从小到大排
15     if(a.len==b.len){
16         return a.wide<b.wide;
17     }
18     else return a.len<b.len;
19 }
20 
21 int main()
22 {
23     int t=0;
24     while( scanf("%d",&n)&&n ){
25         int a,b,c,k=0;
26 
27         while( n-- ){
28             scanf("%d %d %d",&a,&b,&c);//每种都最多有6中摆放方式
29             block[k].len=a; block[k].wide=b; block[k++].high=c;
30             block[k].len=a; block[k].wide=c; block[k++].high=b;
31             block[k].len=b; block[k].wide=a; block[k++].high=c;
32             block[k].len=b; block[k].wide=c; block[k++].high=a;
33             block[k].len=c; block[k].wide=a; block[k++].high=b;
34             block[k].len=c; block[k].wide=b; block[k++].high=a;
35         }
36 
37         sort(block,block+k,cmp);
38         for(int i=0;i<k;i++){
39             ans[i]=block[i].high;
40         }
41 
42         for(int i=0;i<k;i++){//类似于LIS
43             for(int j=0;j<i;j++){
44                 if( block[i].len>block[j].len && block[i].wide>block[j].wide ){
45                     ans[i] = max(ans[i], ans[j]+block[i].high);
46                 }
47             }
48         }
49 
50         sort(ans,ans+k);
51         printf("Case %d: maximum height = %d
",++t, ans[k-1]);
52 
53     }
54     return 0;
55 }