HDU1069 Monkey and Banana(DP)

题目链接

题意:给定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;
}

Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 动态规划