uva437 - The Tower of Babylon（DAG上的DP、LIS）

古城微笑少年丶 2021-12-21 05:45 216阅读 0赞

## 题意：    有几种不同的长方体，每个长方体有无数个，求可以叠起来的最大高度。要求：接触的两个面，下面的面的长宽要分别大于上面的长宽，相等也不可以。 ##

## 思路一： LIS，当成二维偏序问题，**对于每个元素都查一遍他前头有几个符合条件的**。 ##

## 思路二：每种立方体无穷个是没什么用的，其实每种立方体只要三个就够了（当成六种情况也行），每输入一个立方体，就可以算作输入了三个不同的立方体(任选一条边作为高)。然后每一个立方体建边，套用DAG上的dp模板就行了。 ##

## 参考：[https://www.cnblogs.com/AlphaWA/p/9461319.html][https_www.cnblogs.com_AlphaWA_p_9461319.html]、[https://blog.csdn.net/qq\_36300700/article/details/78407323][https_blog.csdn.net_qq_36300700_article_details_78407323]。 ##

## 代码一： ##

#include<bits/stdc++.h>
    using namespace std;
    struct block
    {
        int a;
        int b;
        int height;
        block(int x, int y, int z){a = x; b = y; height = z;}
    };
    
    struct cmp
    {
        bool operator() (const block& x, const block& y)
        {
            return x.a * x.b > y.a * y.b;
        }
    };
    
    bool yes(block x, block y)
    {
        return (x.a > y.a && x.b > y.b) || (x.a > y.b && x.b > y.a);
    }
    
    int main()
    {
        int n, kase = 0;
        while (~scanf("%d", &n) && n)
        {
            vector <block> v;
            for (int i = 0; i < n; i++)
            {
                int a, b, c;
                scanf("%d%d%d", &a, &b, &c);///每块都有三种用法
                v.push_back(block(a,b,c));
                v.push_back(block(a,c,b));
                v.push_back(block(b,c,a));
            }
            sort(v.begin(), v.end(), cmp());
            int ans = v[0].height;
            int dp[100] = {0};
            for (int i = 0; i < v.size(); i++)
            {
                dp[i] = v[i].height;///这是不能省的一步
                ///万一前面没有一个可以匹配的，它本身高度就是本序列的一血
                for (int j = 0; j < i; j++)///前面扫荡一遍
                    if (yes(v[j], v[i]))///双边严格小于
                        dp[i] = max(dp[i], dp[j] + v[i].height);
                ans = max(ans, dp[i]);
            }
            printf("Case %d: maximum height = %d\n", ++kase, ans);
        }
    }

## 代码二： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N=100;
    int n,V[N],d[N],G[N][N],a[3];///V数组保存每一种立方体的高
    ///d数组为以第几个立方体为起点时最大的高度为多少
    ///G数组为标记数组 第i个立方体是否可以作为第j个立方体的底
    struct Cub{
        int x,y;
    } cub[N];
    
    ///注意长宽互换
    void add_edge(int i,int j){
        if(cub[i].x>cub[j].x && cub[i].y>cub[j].y)
            G[i][j]=1;
        if(cub[i].x>cub[j].y && cub[i].y>cub[j].x)
            G[i][j]=1;
    }
    
    int dp(int i)
    {
        int &ans = d[i];
        if(ans > 0) return ans;
        ans=V[i];
        for(int j=0; j<3*n; j++)
            if(G[i][j])
                ans=max(ans,V[i]+dp(j));//特别注意这个V[i]+dp(j)不能写成ans+dp(j)，一开始栽在这里，自己着重理解下。
        return ans;
    }
    
    int main()
    {
        int k=0;
        while(scanf("%d",&n)!=EOF&&n)
        {
            int height=0;
            memset(d,0,sizeof(d));
            memset(G,0,sizeof(G));
            memset(V,0,sizeof(V));
            for(int i=0; i<n; i++)
            {
                scanf("%d%d%d",&a[0],&a[1],&a[2]);
                cub[3*i].x=a[0],cub[3*i].y=a[1],V[3*i]=a[2];
                cub[3*i+1].x=a[0],cub[3*i+1].y=a[2],V[3*i+1]=a[1];
                cub[3*i+2].x=a[1],cub[3*i+2].y=a[2],V[3*i+2]=a[0];
            }
            for(int i=0; i<3*n; i++)
                for(int j=0; j<3*n; j++)
                    add_edge(i,j);
            for(int i=0; i<3*n; i++)
                dp(i);
            for(int i=0 ; i<3*n ; i++)
                height=max(height,d[i]);
            printf("Case %d: maximum height = %d\n",++k,height);
        }
        return 0;
    }

[https_www.cnblogs.com_AlphaWA_p_9461319.html]: https://www.cnblogs.com/AlphaWA/p/9461319.html
[https_blog.csdn.net_qq_36300700_article_details_78407323]: https://blog.csdn.net/qq_36300700/article/details/78407323