Monkey and Banana

1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0

Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342

将每个长方体分离成6个，排序后类似求最大上升子序列。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#include<map>

#define N 100
#define Mod 10000007
#define lson l,mid,idx<<1
#define rson mid+1,r,idx<<1|1
#define lc idx<<1
#define rc idx<<1|1
const double EPS = 1e-11;
const double PI = acos ( -1.0 );
const double E = 2.718281828;
typedef long long ll;

const int INF = 1000010;

using namespace std;

int n,len;
struct edge {
    int c,k,h;
} e[N*3];
int dp[N*3];

bool cmp(edge e1,edge e2)
{
    if(e1.c==e2.c)return e1.k<e2.k;
    return e1.c<e2.c;
}

void add_edge(int x,int y,int z) {
    e[len].c=x;
    e[len].k=y;
    e[len].h=z;
    len++;
}

bool OK(int i,int j) {
    return (e[i].c>e[j].c&&(e[i].k>e[j].k));
}

int main() {
    int ca=1;
    while(cin>>n&&n) {
        len=0;
        int x,y,z;
        for(int i=0; i<n; i++) {
            scanf("%d%d%d",&x,&y,&z);
            add_edge(x,y,z);
            add_edge(x,z,y);
            add_edge(y,z,x);
            add_edge(y,x,z);
            add_edge(z,x,y);
            add_edge(z,y,x);
        }
        sort(e,e+len,cmp);
        int ans=-10100100;
        for(int i=0; i<len; i++) {
            dp[i]=e[i].h;
            for(int j=0; j<=i; j++)
                if(OK(i,j)) {
                    dp[i]=max(dp[i],dp[j]+e[i].h);
                }
            ans=max(ans,dp[i]);
        }
        printf("Case %d: maximum height = %d\n",ca++,ans);
    }
    return 0;
}

hdu 1069 Monkey and Banana(dp)

原文：http://blog.csdn.net/acm_baihuzi/article/details/44492031