| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 586 人关注过本帖
标题:巴比伦之塔
只看楼主 加入收藏
lishizelibin
Rank: 2
等 级:论坛游民
帖 子:513
专家分:41
注 册:2007-5-10
结帖率:100%
收藏
 问题点数:0 回复次数:5 
巴比伦之塔

巴比伦人有N种石块,每种石块的数量均为无限。石块是长方体,每种石块的三维分别为xi,yi,zi。石块可以任意转动。巴比伦人想用这些石块造出一个尽可能高的塔。当然,不是说石块数量无限塔的高度也就无限了,塔的建造是要符合自然规律的――放在上面的石块的地面的两维必须分别严格小于放在下面的石块的底面两维。严格小于就是指不能相等。比如,一个底面为3×3的石块不能放在底面为3×3、2×4、1×2的石块上面,但是能放在底面为4×5的石块上面。也就是说,同样类型的石块如果不进行旋转是没办法叠起来的。

输入格式:
输入包含多组数据,每组数据相互独立。对于每组数据,第一行有一个整数N(N <= 30),表示有N种石块。接下来的n行,每行三个空格分隔的整数,描述每个石块的三维xi、yi、zi。最后一组数据N为0,表示整个输入结束。该组数据不需要被处理。

输出格式:
对于每组数据,输出仅一行,上面一个整数,表示巴比伦之塔最高能造多少高。



附:
我有三个问题:
第一,我发的帖没人回,要发什么样的帖???
第二,对前途担忧,从事IT行业,我该具备什么???
第三,对c语言的学习,想更深,你够给个提升的指导么,书籍,相关提升的c内容???

[此贴子已经被作者于2007-8-3 22:55:47编辑过]

搜索更多相关主题的帖子: 巴比伦 长方体 
2007-08-03 22:04
lishizelibin
Rank: 2
等 级:论坛游民
帖 子:513
专家分:41
注 册:2007-5-10
收藏
得分:0 

高手,点拨一下吧,记得高中看过这辅导书


惟有学习不断的学习!
2007-08-03 22:57
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
动态规划吧

汗,都懒得写代码了.......... cheat了一个威望,哈.....
2007-08-03 23:15
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
收藏
得分:0 

d[i][j]表示第i次放第j快的高度
那么应该有 d[i][j]=max(d[i-1][j from 0 to n]&&(符合严格小于))+1
准确的说状态应该用d[i][j][k],k表示石头的放法.
这里没种石头最多用3次所以i 最多到n*3
最后可以找数组中的最大值或者在计算过程中纪录下来..

楼上似乎好久没来了
我DP也不好楼上看看对不??


2007-08-04 03:17
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
以下是引用crackerwang在2007-8-4 3:17:35的发言:

d[i][j]表示第i次放第j快的高度
那么应该有 d[i][j]=max(d[i-1][j from 0 to n]&&(符合严格小于))+1
准确的说状态应该用d[i][j][k],k表示石头的放法.
这里没种石头最多用3次所以i 最多到n*3
最后可以找数组中的最大值或者在计算过程中纪录下来..

楼上似乎好久没来了
我DP也不好楼上看看对不??

错了,没那么复杂吧-_-
先按x从小到大排序,若x相等,则按y从小到大排,
然后就是在y维进行类似最长递增子序列的dp了
d[j]=max(d[i]+z[j]) i<j&&y[i]<y[j]


汗,都懒得写代码了.......... cheat了一个威望,哈.....
2007-08-04 18:38
crackerwang
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:833
专家分:0
注 册:2007-2-14
收藏
得分:0 
楼上正解

2007-08-05 01:43
快速回复:巴比伦之塔
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.094146 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved