HDU 1069動的計画(DP)Monkey and Banana

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1069
題意:n(n<=30)種の異なる立方体(個数に限りません)があり、  どれだけの高さを積むことができることを求めます.
分析:
(1)各立方体について、長い、幅、高さが互いに等しくないと仮定すると、その配置方法は6つの異なる場合(長、幅、高全配列)がある.
(2)では、実際には6*n種の異なる立方体と見なすことができる.
(3)この6*n種の立方体の長い(長さ等であれば幅)を大きく並べ替える. 
(4)ここにはたくさんの箱が並んでいるのと同じように、どうやって一番高く積み上げるかを見てみましょう.
(5)小さい頃から、後ろの箱の上に前の小さいのを置くことができれば、その小さいのを大きな箱の上に置く.
(6)そしてこの山を一つの箱と見なして、ただこの箱は以前より高くなったが、底面は変わらない.
(7)(6)の操作を繰り返す.最後に何の位置もない箱をその位置の箱の上に置くことができるまで,一番高いのが答えだ!
 

#include<iostream>

#include<string>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<cmath>

using namespace std;

const int maxn=10000;



struct node

{

    int x,y;

    int h;

} dp[maxn];



bool cmp(node A, node B)

{

    if(A.x==B.x) return A.y<B.y;

    return A.x<B.x;

}



int main()

{

    int n,cas=1;

    while(cin>>n&&n)

    {

        int N=0;

        for(int i=0; i<n; ++i)

        {

            int a,b,c;

            cin>>a>>b>>c;

            dp[N].x=a, dp[N].y=b, dp[N].h=c, ++N;

            dp[N].x=b, dp[N].y=a, dp[N].h=c, ++N;

            dp[N].x=c, dp[N].y=b, dp[N].h=a, ++N;

            dp[N].x=b, dp[N].y=c, dp[N].h=a, ++N;

            dp[N].x=a, dp[N].y=c, dp[N].h=b, ++N;

            dp[N].x=c, dp[N].y=a, dp[N].h=b, ++N;

        }

        sort(dp,dp+N,cmp);

        int ans=dp[0].h;

        for(int i=1; i<N; ++i)

        {

            int temp=0;

            for(int j=0; j<i; ++j)

                if( dp[i].x>dp[j].x && dp[i].y>dp[j].y )

                    temp=max(temp,dp[j].h);

            dp[i].h += temp;

            ans = max( ans, dp[i].h );

        }

        printf("Case %d: maximum height = %d
",cas++,ans);

    }

    return 0;

}