HDOJ 1069 DP

HDOJ 1069 DP

开启DP之路

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1069
 描述一下：

就是给定N(N<=20)个方体，让你放置，求放置的最高高度，限制条件是：上面的物体的长度和宽度都小于下面物体。

觉得这道题目很经典：

于是贴下

。

我们可以把一个方体看成六个，想到这里，然后求最高,方程很简单了 ，

 if (a[j].x>a[i].x&&a[j].y>a[i].y)             ans=max(ans,a[j].h+a[i].h);             a[i].h=ans;#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

struct node

{

    int x,y,h;

}a[];

int cmp(node x,node y)

{

    if (x.x==y.x) return x.y>y.y;

    return x.x>y.x;

}

int main()

{

    int n;

    int t=;

    while (scanf("%d",&n)!=EOF)

    {

        t++;

        if (n==) break;

        int xx,yy,zz,nn=;

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

        {

            scanf("%d%d%d",&xx,&yy,&zz);

            a[++nn].x=xx;a[nn].y=yy;a[nn].h=zz;

            a[++nn].x=xx;a[nn].y=zz;a[nn].h=yy;

            a[++nn].x=yy;a[nn].y=xx;a[nn].h=zz;

            a[++nn].x=yy;a[nn].y=zz;a[nn].h=xx;

            a[++nn].x=zz;a[nn].y=yy;a[nn].h=xx;

            a[++nn].x=zz;a[nn].y=xx;a[nn].h=yy;

        }

        sort(a+,a+nn+,cmp);

        a[].h=;

        a[].x=a[].y=;

        for (int i=;i<=nn;i++)

        {

            int ans=;

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

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

            ans=max(ans,a[j].h+a[i].h);

            a[i].h=ans;

        }

        int ans=;

        for (int i=;i<=nn;i++)

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

        printf("Case %d: maximum height = %d\n",t,ans);

    }

    return ;

}

求出A[1].H--A[N].H的最大ok了