HDU Monkey and Banana

Monkey and Banana

点击(此处)折叠或打开

/*

#include<stdio.h>
#include<string.h>
struct Box{
    int x;
    int y;
    int z;
    int area;
}box[91];
void change(int &a,int &b)
{
    int temp;
    temp=a;a=b;b=temp;
}
void cmp(int &x,int &y,int &z)
{
    if(x<y)change(x,y);
    if(x<z)change(x,z);
    if(z>y)change(z,y);
}
int cmp2(int n)
{
    Box temp;
    int i,j;
    for(i=0;i<=n;i++)
    {
        for(j=1;j<n-i;j++)
           if(box[j].area<box[j+1].area)
           {
              temp=box[j];box[j]=box[j+1];box[j+1]=temp;
           }
    }
}
int main()
{
    int n,i,j;
    int a,b,c;
    int dp[91],big=0,len,test=1;
    while(scanf("%d",&n)&&n!=0)
    {
        for(i=0,j=0;i<n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);cmp(a,b,c);
            box[++j].x=a;box[j].y=b;box[j].z=c;box[j].area=a*b;
            if(a!=b)
            {
              box[++j].x=a;box[j].y=c;box[j].z=b;box[j].area=a*c;
              box[++j].x=b;box[j].y=c;box[j].z=a;box[j].area=b*c;
            }
        }
        len=j;
        cmp2(len);
     for(i=1;i<=len;i++)
        dp[i]=box[i].z;
      for(i=1;i<=len;i++)
      {
        for(j=1;j<i;j++)
        {

            if(box[i].x<box[j].x&&box[i].y<box[j].y)
                dp[i]=dp[i]>(dp[j]+box[i].z)?dp[i]:(dp[j]+box[i].z);
        }
        if(big<dp[i])big=dp[i];
    }
    printf("Case %d: maximum height = %d\n",test++,big);
    big=0;
    }
}
*/



//#define local

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;

typedef struct box
{
    int l;
    int w;
    int h;
}box;

int re[1000][1000];
box t[1000];
int nb = 0;

int cmp1(const int a, const int b)
{
    return a>b;
}

void fun(int q[])
{
    sort(q,q+3,cmp1);


        nb++;
        t[nb].l = q[0];
        t[nb].w = q[1];
        t[nb].h = q[2];
        nb++;
        t[nb].l = q[1];
        t[nb].w = q[2];
        t[nb].h = q[0];
        nb++;
        t[nb].l = q[0];
        t[nb].w = q[2];
        t[nb].h = q[1];   //一直WA,后来大神提点原来这里错了

}

int cmp2(const box a,const box b)
{
    if(a.l == b.l)
        return a.w > b.w;
    return a.l > b.l;
}

int main()
{
    int n;
    int i,j,k;
    int a[3];
    int ca = 0;

    int sum = 0;
// int next = 0;
#ifdef local
    freopen("in.txt","r",stdin);
#endif // local



    while(scanf("%d",&n)!=EOF && n!=0)
    {
        ca++;
        nb = 0;
        sum = 0;
        memset(t,0,sizeof(box)*1000);
        memset(re,0,sizeof(int)*1000000);

        for(i = 0; i < n; i++)
        {
            scanf("%d%d%d",&a[0],&a[1],&a[2]);
            fun(a);
        }
        sort(t+1,t+nb+1,cmp2);

        for(i = 1; i<= nb; i++)
        {
            re[nb][i] = t[i].h;

        }

        for(i = nb - 1; i >= 1; i--)//第i层，又顶开始算
        {
            for(k = 1; k <= nb; k++) //第k个
            {
                for(j = k+1;j <= nb; j++) //与下一层的累加，求最大
                {
                    if(t[k].w > t[j].w && t[k].l > t[j].l)
                    {
                         re[i][k] = max(re[i][k],re[i+1][j] + t[k].h);
                    }
                }
            }
        }
        for(i = 1; i <= nb; i++)
        {
            for(j = 1; j <= nb; j++)
            {
                if(re[i][j] > sum)
                    sum = re[i][j];
            }
        }

        printf("Case %d: maximum height = %d\n",ca,sum);
    }
    return 0;
}