HDU 1069 Monkey and Banana

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

题目意思：给n种箱子，每种有足够多的箱子，把箱子从下往上叠，要求下面的要比上面的长宽都要大，问最高叠多高。

分析：每种箱子有3种状态，记录完后，简单dp(最长上升子序列)。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct b
{
    int x, y, h;
}box[100];

bool cmp(b t1, b t2)
{
    return t1.x*t1.y < t2.x*t2.y;
}
int dp[1000000];

int main()
{
    int n;
    int kk = 1;
    while(scanf("%d", &n), n)
    {
        int H = 0;
        for(int i=0; i<n; i++)
        {
            scanf("%d %d %d", &box[i*3].x, &box[i*3].y, &box[i*3].h);
            box[i*3+1].x = box[i*3].x, box[i*3+1].y = box[i*3].h, box[i*3+1].h = box[i*3].y;
            box[i*3+2].x = box[i*3].h, box[i*3+2].y = box[i*3].y, box[i*3+2].h = box[i*3].x;
        }
        int k = n*3;
        sort(box, box+k, cmp);
        memset(dp, 0, sizeof(dp));
        int ans = 0;
        dp[0] = 0;
        for(int i=0; i<k; i++)
        {
            dp[i] = box[i].h;
            int Max = 0;
            for(int j=i-1; j>=0; j--)
            {
                if(box[i].x>box[j].x&&box[i].y>box[j].y || box[i].x>box[j].y&&box[i].y>box[j].x)
                Max = max(Max, dp[j]);
            }
            dp[i] += Max;
            if(dp[i]>ans)
                ans = dp[i];
        }
        printf("Case %d: maximum height = %d
", kk++, ans);
    }

    return 0;
}