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

浅浅的花香味﹌ 2024-02-17 19:14 37阅读 0赞

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

AC代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=30+2;
    struct node{
    	int x,y,z;
    	node(int x=0,int y=0,int z=0):x(x),y(y),z(z){}
    	bool operator<(const node& n)const {
    		return x<n.x&&y<n.y || x<n.y&&y<n.x;
    	}
    }nt[maxn*3];
    int g[maxn*3][maxn*3];
    int d[maxn*3];
    int n;
    
    int dp(int i,int h){
    	int& ans=d[i];
    	if(ans>0)return ans;
    	ans=h;
    	for(int j=0;j<n*3;j++)
    	if(g[i][j])ans=max(ans,dp(j,nt[j].z)+h);
    	return ans;
    }
    int main(){
    	int count1=0;
    	while(scanf("%d",&n)==1 && n){
    		int c=0;
    		for(int i=0;i<n;i++){
    			int x,y,z;
    			scanf("%d%d%d",&x,&y,&z);
    			nt[c++]=node(x,y,z);  //第三位表示高度 
    			nt[c++]=node(x,z,y);
    			nt[c++]=node(y,z,x);
    		}	
    		memset(d,0,sizeof(d));
    		memset(g,0,sizeof(g));
    		for(int i=0;i<n*3;i++)
    		 for(int j=0;j<n*3;j++)
    		  if(nt[i]<nt[j])g[i][j]=1;
    		  
    		  int ans=-1e5;
    		  for(int i=0;i<n*3;i++)
    		   ans=max(ans,dp(i,nt[i].z));
    		printf("Case %d: maximum height = %d\n",++count1,ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 uva 437——The Tower of Babylon

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

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

相关动态规划：数塔问题

动态规划问题我训练过一些题目，但是感觉自己掌握的还不是特别好！下面以一道经典的动态规划题目说明动态规划算法的思想，文末会官方的给出对动态规划的文字叙述。先看题目：如下

本是古典何须时尚/ 2022年08月08日 12:49/ 0 赞/ 201 阅读

相关 uva 437 动态规划

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

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

相关 uva 116 数塔动态规划

横着的数塔，从左往右走，可以走右上，右，右下三个方向，最后一行往右下走可以穿越到第一行，第一行往右上走可以穿越到最后一行。最后要求输出走的路径以及路径和的最小值，

亦凉/ 2022年08月03日 13:41/ 0 赞/ 197 阅读

相关 uva 10003 动态规划

给定一个长度为len的木板，要在n个位置处切开，每次切开的代价是这块木板的长度，求最小的代价。其实切木板跟合并木板是等价的。。开始以为是简单的贪心，便写了一个优先

待我称王封你为后i/ 2022年08月03日 13:41/ 0 赞/ 9 阅读

相关 uva 11584 动态规划

给定一串字符串，看最少能把它分成几个回文字符串。 SampleInput 3 racecar fastcar aaadbccb SampleOutput 1 7

向右看齐/ 2022年08月03日 13:41/ 0 赞/ 7 阅读

相关动态规划（入门级）-数塔

题目：数塔 Description 在讲述DP

我就是我/ 2022年05月15日 03:13/ 0 赞/ 230 阅读

相关动态规划（1）：数塔问题

题目一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字… 第n 层有n 个数字。现在要从第一层走到第n 层，每次只能走向下一层连接的两个数字中的一个，问：最

Dear 丶/ 2022年02月09日 14:37/ 0 赞/ 258 阅读

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

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

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