UVA437 The Tower of Babylon 动态规划 - c++编程基础

题意：给你N种立方体，每种立方体个数不限，让你堆塔，求塔最大高度，堆塔的条件是每一个立方体的长和宽必须严格大于它下面的立方体的长和宽，因为每个立方体个数无限，所以必须要进行排序了，不需要按照堆塔的条件来排序，可以按照底面积的大小来排，原因很简单，还有因为立方体个数无限，外加堆塔条件限制，其实就是每一种立方体又可以演变成六种立方体，因为没有固定哪个是高宽长，都处理好以后，一看就是一个类似于 LIS 的问题，只不过长度每次的+1 变成了+当前立方体的高罢了，敲起来很快

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[100000 + 5]; struct Node { int l,w,h; void cal(int x,int y,int z) { l = x,w = y, h = z; } }node[100000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(node,0,sizeof(node)); } bool cmp(Node x,Node y) { return x.l * x.w < y.l * y.w; } int main() { int n; int Case = 0; while(scanf("%d",&n),n) { clear(); int tot = 0; for(int i=1;i<=n;i++) { int x,y,z; scanf("%d %d %d",&x,&y,&z); node[++tot].cal(x,y,z); node[++tot].cal(x,z,y); node[++tot].cal(y,x,z); node[++tot].cal(y,z,x); node[++tot].cal(z,x,y); node[++tot].cal(z,y,x); } sort(node + 1,node + tot,cmp); for(int i=1;i<=tot;i++) dp[i] = node[i].h; int ans = 0; for(int i=2;i<=tot;i++) { for(int j=1;j
                    
                      node[j].l && node[i].w > node[j].w) dp[i] = max(dp[i],dp[j] + node[i].h); } if( ans < dp[i]) ans = dp[i]; } printf("Case %d: maximum height = %d\n",++Case,ans); } return EXIT_SUCCESS; }