hdu1069Monkey and Banana(最长递增子序列)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1069

参考别人的。

因为箱子可以翻转且要求严格递增，所以一个箱子可以当做三个箱子。

将箱子按长宽从大到小排序，就成了最长递增子序列问题。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=35;
 6 int dp[maxn*3];
 7 int n;
 8 struct node
 9 {
10     int l,w,h;
11     node(int l,int w,int h):l(l),w(w),h(h){}
12     node(){};
13     bool operator<(const node& a)
14     {
15         if(l==a.l) return w>a.w;
16         return l>a.l;
17     }
18 }p[maxn*3];
19 
20 int main()
21 {
22     int cas=0;
23     while(scanf("%d",&n)&&n)
24     {
25         int l,w,h;
26         int cnt=0;
27         int ans=0;
28         for(int i=0;i<n;i++)
29         {
30             scanf("%d%d%d",&l,&w,&h);
31             p[cnt++]=node(max(l,w),min(l,w),h);   //注意max和min不可省去，因为堆起来的时候肯定 长边对长边 短边对短边
32             p[cnt++]=node(max(w,h),min(w,h),l);   //如果此处不调整长宽，则下面判断是否可以堆叠时会出错
33             p[cnt++]=node(max(h,l),min(h,l),w);   //比如 长宽为（6,8）和（7,5）本来可以放，若不调整则会判为无法放
34         }
35         sort(p,p+cnt);
36         dp[0]=p[0].h;
37         ans=dp[0];
38         for(int i=1;i<cnt;i++)
39         { 
40             dp[i]=p[i].h;   //因为没有写这行一直WA，，因为有可能第i个箱子无法堆叠到前面箱子上
41             for(int j=0;j<i;j++)
42             if(p[j].l>p[i].l&&p[j].w>p[i].w)
43                     dp[i]=max(dp[i],dp[j]+p[i].h);
44             ans=max(dp[i],ans);
45         }
46         printf("Case %d: maximum height = %d
",++cas,ans);
47     }
48 
49 }