C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

hdu 1069 Monkey and Banana NYOJ 232 (简单DP)

Posted on 2012-03-23 10:37 C小加 阅读(404) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

题意:把给定尺寸的长方体(数量不限)叠加在一起,叠加的条件是,上面一个长方体的长和宽比下面长方体的长和宽短,不能相等,长方体可以任意面朝下摆放,求这些长方体能叠加的最高的高度。

 

把每个长方体分成3个元素。然后就和矩形嵌套差不多了,排序之后求容量最大的子序列。


    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;

    typedef struct
    {
        int l,w,h;
    }Cub;
    Cub cub[31*3];
    int n;
    int cnt;
    int f[31*3];
    bool cmp(Cub c1,Cub c2)
    {
        if(c1.l==c2.l) return c1.w<c2.w;
        return c1.l<c2.l;
    }

    bool input()
    {
        scanf("%d",&n);
        if(!n) return false;
        cnt=0;
        int l,w,h;
        for(int i=0;i<n;i++)
        {
            scanf("%d %d %d",&l,&w,&h);
            cub[cnt].h=l;
            cub[cnt].w=w>h?h:w;
            cub[cnt].l=w>h?w:h;
            cnt++;
            cub[cnt].h=w;
            cub[cnt].w=l>h?h:l;
            cub[cnt].l=l>h?l:h;
            cnt++;
            cub[cnt].h=h;
            cub[cnt].w=l>w?w:l;
            cub[cnt].l=l>w?l:w;
            cnt++;
        }
        return true;
    }

    void DP()
    {
        memset(f,0,sizeof(f));
        for(int i=0;i<cnt;i++) f[i]=cub[i].h;
        for(int i=1;i<cnt;i++)
        {
            for(int j=0;j<i;j++)
            {
                if((cub[i].l!=cub[j].l)&&(cub[i].w>cub[j].w))
                {
                    f[i]=max(f[i],f[j]+cub[i].h);
                }

            }
        }
    }

    void print()
    {
        static int pos=0;
        int ans=0;
        for(int i=0;i<cnt;i++)
        ans=max(f[i],ans);
        printf("Case %d: maximum height = %d\n",++pos,ans);
    }

    int main()
    {
        while(input())
        {
            sort(cub,cub+cnt,cmp);
            //for(int i=0;i<cnt;i++)
            
//    printf("%d %d %d\n",cub[i].l,cub[i].w,cub[i].h);
            DP();
            print();


        }

        return 0;
    }

   

 


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理