HDU1069 Monkey and Banana（DP）

February 17, 2016

题目链接

题意：给定 n 个型号的砖头，和他们的长宽高，也就是说一种型号有三种摆放方法。要求摆出最高高度的砖头堆，使相邻的两个砖头上面的长和宽分别小于下面的长和宽。

每个型号有三种砖头，3*n 种砖头存入结构体（长大于宽），然后按长排序，若相等按宽排序。dp[i]表示以第 i 种砖头为顶点的最大高度，那么可以写出状态转移方程：dp[j] = max(dp[j], dp[i]+h[j]) ，其中 j 是 i 上面的砖头，h[j]代表第 j 种砖头的高度。

#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
using namespace std;

int dp[100];

struct node{
    int a, b, h;
}N[100];

bool cmp(node x, node y){
    if(x.a == y.a) return x.b < y.b;
    else return x.a < y.a;
}

int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    int cas = 0;
    while(scanf("%d", &n) != EOF && n){
        int num = 0;
        while(n--){
            int a[3];
            scanf("%d %d %d", &a[0], &a[1], &a[2]);
            sort(a, a+3);
            N[num].a = a[0];
            N[num].b = a[1];
            N[num++].h = a[2];

            N[num].a = a[0];
            N[num].b = a[2];
            N[num++].h = a[1];

            N[num].a = a[1];
            N[num].b = a[2];
            N[num++].h = a[0];
        }
        sort(N, N+num, cmp);
        for(int i = 0; i < num; i++)
            dp[i] = N[i].h;
        for(int i = 0; i < num; i++){
            for(int j = i+1; j < num; j++){
                if(N[j].a > N[i].a && N[j].b > N[i].b)
                    dp[j] = max(dp[j], dp[i]+N[j].h);
            }
        }
        int ans = 0;
        for(int i = 0; i < num; i++)
            ans = max(ans, dp[i]);
        printf("Case %d: maximum height = %dn", ++cas, ans);
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]