uva 437——The Tower of Babylon

r囧r小猫 2022-08-14 05:48 136阅读 0赞

题意：给定n个长方体，然后堆积最高的塔，要求上面的面积小于下面的面积。

思路：Dp，先把长方体的所有放的情况都构造出来放到数组里，对于当前节点，如果能够在前面找到面积比当前小，高度累加比当前高的则转移状态。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    #define ft(i,s,t) for(int i=s;i<=t;i++)
    
    const int N=95;
    struct node
    {
        int x,y,h;
    }g[N];
    int dp[N],v[3];
    
    bool cmp(node a,node b){
        if (a.x==b.x) return a.y<b.y;
        return a.x<b.x;
    }
    int main()
    {
        int n,ca=1;
        while(~scanf("%d",&n),n)
        {
            int l=0;
             ft(j,0,n-1){
                 ft(i,0,2) scanf("%d",&v[i]);
                 sort(v,v+3);
                 ft(i,0,2)
                 {
                     g[l+i].h=v[(0+i)%3];
                     g[l+i].x=v[(2+i)%3];
                     g[l+i].y=v[(1+i)%3];
                 }
                 swap(g[l+1].x,g[l+1].y);
                 l+=3;
             }
    
             sort (g,g+l,cmp);
             int ans=0;
             ft(i,0,l-1)
             {
                 dp[i]=g[i].h;
                 for (int j=0;j<i;j++)
                 {
                     if (g[j].x<g[i].x&&g[j].y<g[i].y&&dp[i]<dp[j]+g[i].h)
                        dp[i]=dp[j]+g[i].h;
                 }
                 ans=max(ans,dp[i]);
             }
             printf("Case %d: maximum height = %d\n",ca++,ans);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，136人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 437 The Tower of Babylon 巴比伦塔（DAG上的动态规划）

题意：给n中立方体，每种无限多个，求能堆成塔的最高高度（必须严格满足上面的长宽小于下面的） AC代码如下： include<cstdio> include<

浅浅的花香味﹌/ 2024年02月17日 19:14/ 0 赞/ 36 阅读

相关 UVA 12333 Revenge of Fibonacci

题目链接：[https://vjudge.net/problem/UVA-12333][https_vjudge.net_problem_UVA-12333] 题意摘自《算法

川长思鸟来/ 2023年06月04日 14:54/ 0 赞/ 52 阅读

相关 uva 437——The Tower of Babylon

题意：给定n个长方体，然后堆积最高的塔，要求上面的面积小于下面的面积。思路：Dp，先把长方体的所有放的情况都构造出来放到数组里，对于当前节点，如果能够在

r囧r小猫/ 2022年08月14日 05:48/ 0 赞/ 137 阅读

相关 uva 1614——UVA 1614 - Hell on the Markets

Description [![Download as PDF][]][Download as PDF 1]Most financial institutions had be

客官°小女子只卖身不卖艺/ 2022年08月09日 14:56/ 0 赞/ 105 阅读

相关 pku 3601 Tower of Hanoi

\include <stdio.h> int m\[110\],F\[110\], G\[110\]; int main() \{ int i, N, M; while(sca

分手后的思念是犯贱/ 2022年08月08日 19:46/ 0 赞/ 120 阅读

相关 uva 437 动态规划

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

青旅半醒/ 2022年08月03日 13:42/ 0 赞/ 162 阅读

相关 UVA 1593 Alignment of Code

You are working in a team that writes Incredibly Customizable Programming Codewriter (IC

你的名字/ 2022年06月07日 01:25/ 0 赞/ 157 阅读

相关 Strange Towers of Hanoi (POJ1958)

Strange Towers of Hanoi (POJ1958) n个盘子4座塔的Hanoi问题至少需要多少步？(1<=n<=12) 分析： n盘3塔: \\(d\[n

柔光的暖阳◎/ 2021年12月22日 15:34/ 0 赞/ 179 阅读

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

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

古城微笑少年丶/ 2021年12月21日 05:45/ 0 赞/ 215 阅读

相关 UVA 11292 - The Dragon of Loowater (water)

[http://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&category=24&page=

柔情只为你懂/ 2021年11月19日 15:44/ 0 赞/ 149 阅读