Monkey and Banana

C - Monkey and Banana

参考：ACM HDU 1069 Monkey and Banana (动态规划）

思路：对于这道DP题来说，如果以高度或者说砖块的个数来作为储存的状态的内容，显然是不合适的。

不难看出，这道题主要是想求一个最长有序子序列，那么我们首先把所有可能的长宽高都保存起来，然后再对该数组求一个最长有序子序列即可！

只要理解了什么是最长有序子序列，那么该题便迎刃而解！

代码：

// Created by CAD on 2019/10/17.
#include <bits/stdc++.h>
using namespace std;

struct BOX{
    int x,y;
    int high,dp;
    bool operator<(BOX &b)
    {
        if(x<b.x)   return true;
        return x==b.x && y<b.y;
    }
}box[200];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,Case=0;
    while(cin>>n,n)
    {
        int cnt=0;
        for(int i=1;i<=n;++i)
        {
            int x,y,z;  cin>>x>>y>>z;
            box[++cnt].x=x,box[cnt].y=y,box[cnt].high=box[cnt].dp=z;
            box[++cnt].x=x,box[cnt].y=z,box[cnt].high=box[cnt].dp=y;
            box[++cnt].x=y,box[cnt].y=x,box[cnt].high=box[cnt].dp=z;
            box[++cnt].x=y,box[cnt].y=z,box[cnt].high=box[cnt].dp=x;
            box[++cnt].x=z,box[cnt].y=x,box[cnt].high=box[cnt].dp=y;
            box[++cnt].x=z,box[cnt].y=y,box[cnt].high=box[cnt].dp=x;
        }
        sort(box+1,box+cnt+1);
        int ans=0;
        for(int i=1;i<=cnt;++i)
            for(int j=1;j<=cnt;++j)
            {
                if(box[i].x>box[j].x&&box[i].y>box[j].y)
                    box[i].dp=max(box[j].dp+box[i].high,box[i].dp);
                ans=max(ans,box[i].dp);
            }
        cout<<"Case "<<++Case<<": maximum height = "<<ans<<endl;
    }
    return 0;
}