uva 437 动态规划

青旅半醒 2022-08-03 13:42 183阅读 0赞

给定一些立方体，每种立方体有长宽高三个属性，可以任意变换摆放姿势，每种立方体有无限个，要把其中的一些摆起来，求最大的高度。要求在上面的立方体必须底部的长宽都小于在下面的立方体的顶部的长宽。

可以把一个立方体当成三个存到数组中，x,y,z轮换着当高，剩下的两个随便当长或者宽就行。

先把他们按照面积从小到大排序，因为面积大的一定在面积小的下面，这样就避免漏掉一些。

然后就是类似于求最长上升子序列了。

//uva 437
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<ll,ll> pll;
    
    inline ll in()
    {
        ll res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    ll dp[99];
    struct st
    {
        ll x,y,z;
    }a[99];
    bool cmp(const st& a,const st &b)
    {
        return ll(a.x*a.y)<ll(b.x*b.y);
    }
    
    int main()
    {
        int n,T=1;
        while(~scanf("%d",&n) && n)
        {
            for(int i=1;i<=n;i++)
            {
                ll x=in(),y=in(),z=in();
                a[i].x=x;
                a[i].y=y;
                a[i].z=z;
                a[++i].x=x;
                a[i].y=z;
                a[i].z=y;
                a[++i].x=z;
                a[i].y=y;
                a[i].z=x;
                n+=2;
            }
            sort(a+1,a+1+n,cmp);
            for(int i=1;i<=n;i++)
            {
                dp[i]=a[i].z;
            }
            ll ans=0;
            for(int i=1;i<=n;i++)
            {
    
                for(int j=1;j<i;j++)
                {
                    if((a[j].x<a[i].x && a[j].y<a[i].y) || (a[j].x<a[i].y && a[j].y < a[i].x))
                    {
                        dp[i]=max(dp[i],dp[j]+a[i].z);
                    }
                }
                ans=max(dp[i],ans);
    
            }
    
            printf("Case %d: maximum height = %lld\n",T++,ans);
        }
        return 0;
    }