HDU 1069 – Monkey and Banana

动态规划基础题,以前做过一道类似的,不过是01的,这次是完全的。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct Cube{
    int x, y, z;
    Cube(int x = 0, int y = 0, int z = 0):x(x), y(y), z(z){}
    bool operator < (const Cube & rhs) const {
        return x==rhs.x ? y > rhs.y : x > rhs.x;
    }
};
int dp[128];
Cube v[128];

int main()
{
    int n, kase = 0;
    while(cin >> n, n){
        int cnt = 1; memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; ++i){
            int l[3]; cin >> l[0] >> l[1] >> l[2]; sort(l, l + 3);
            v[cnt++] = Cube(l[2], l[1], l[0]);
            v[cnt++] = Cube(l[1], l[0], l[2]);
            v[cnt++] = Cube(l[2], l[0], l[1]);
        }
        sort(v + 1, v + cnt);
        for(int i = 1; i < cnt; ++i)
            for(int j = 0; j < i; ++j)
                if(j==0 || (v[i].x < v[j].x && v[i].y < v[j].y))
                    dp[i] = max(dp[i], dp[j] + v[i].z);
        printf("Case %d: maximum height = %d\n", ++kase, *max_element(dp+1, dp+cnt));
    }
    return 0;
}

 

欢迎留言