例题9-2 巴比伦塔（The Tower of Babylon, UVa 437）

欢迎访问我的Uva题解目录 https://blog.csdn.net/ri*qi/article/details/81149109

题目描述

题意解析

有n（n≤30）种立方体，每种都有无穷多个。要求选一些立方体摞成一根尽量高的柱子（可以自行选择哪一条边作为高），使得每个立方体的底面长宽分别严格小于它下方立方体的底面长宽。

算法设计

建立一个结构体表示每一个block。注意由于block的任意一边均可作长宽高，对于给定的一个block来说，可以6种不同的柱子。将所有不同的柱子存储在vector<Block>blocks中，以下标标志唯一的blocks中的一个柱子。
然后以柱子在blocks中的下标为结点编号，按照长宽的大小关系建立边，构成一个DAG图，整个问题就变成了求解DAG最长路问题。用数组dp[i]表示以结点i为起点的最长路长度，则状态转移方程为$dp(i)=max \{ dp(i),blocks[i].z+dp(j)\}$dp(i)=max{dp(i),blocks[i].z+dp(j)}
具体实现可见代码。

C++代码

#include<bits/stdc++.h>
using namespace std;
struct Block{
    int x,y,z;//长宽高
    Block(int a,int b,int c):x(a),y(b),z(c){}
};
int n;
vector<Block>blocks;//存储所有可能摆放的立方体
int DP(int v,vector<int>&dp){
    if(dp[v]!=0)//该结点已计算过，直接返回值
        return dp[v];
    dp[v]=blocks[v].z;//dp数组初始化为对应立方体的高
    for(int i=0;i<blocks.size();++i)//遍历所有立方体
        if(blocks[i].x>blocks[v].x&&blocks[i].y>blocks[v].y)//当前遍历到的立方体长宽更大
            dp[v]=max(dp[v],blocks[v].z+DP(i,dp));//计算最大高度
    return dp[v];
}
int main(){
    for(int ii=1;~scanf("%d",&n)&&n!=0;++ii){
        blocks.clear();
        for(int i=0;i<n;++i){
            int a[3];
            scanf("%d%d%d",&a[0],&a[1],&a[2]);
            for(int i=0;i<3;++i)//找出所有可以摆放的立方体
                for(int j=0;j<3;++j)
                    for(int k=0;k<3;++k)
                        if(i!=j&&i!=k&&j!=k)
                            blocks.push_back(Block(a[i],a[j],a[k]));
        }
        int ans=0;
        vector<int>dp(blocks.size(),0);
        for(int i=0;i<blocks.size();++i)//计算出以各节点为起点的最大高度，并求出这些最大高度中的最大高度
            ans=max(ans,DP(i,dp));
        printf("Case %d: maximum height = %d\n",ii,ans);
    }
    return 0;
}