HDU 1069—— Monkey and Banana——————【dp】

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn = 1000;
struct Cube{
    int a,b,h;
}cube[maxn];
int dp[maxn];
bool cmp(Cube a,Cube b){
    if(a.a == b.a)
        return a.b < b.b;
    return a.a < b.a;
}
int main(){
    int n,cnt = 0;
    while(scanf("%d",&n)!=EOF&&n){
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= 3*n; i+=3){
            int aa,bb,cc;
            scanf("%d%d%d",&aa,&bb,&cc);
            for(int j = 0; j < 3; j++){
                if(j == 1)
                    swap(aa,cc);
                if(j == 2)
                    swap(bb,cc);
                cube[i+j].a = aa;
                cube[i+j].b = bb;
                if(cube[i+j].a > cube[i+j].b){
                    swap(cube[i+j].a,cube[i+j].b);
                }
                cube[i+j].h = cc;
            }
        }
        sort(cube+1,cube+1+3*n,cmp);
        for(int i = 1; i <= 3*n;i ++){
            dp[i] = cube[i].h;
        }
        for(int i = 1; i <= 3*n; i++){
            for(int j = i+1; j <= 3*n; j++){
                if(cube[j].a > cube[i].a && cube[j].b > cube[i].b){
                    dp[j] = max(dp[j],dp[i]+cube[j].h);
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= 3*n;i++)
            ans = max(ans,dp[i]);
        printf("Case %d: maximum height = %d\n",++cnt,ans);
    }
    return 0;
}