作者aecho (星空下的呢喃)
看板ACMCLUB
标题acm 103
时间Fri Mar 21 13:29:19 2003
Problem 103
题目：
堆箱子，根据题目所给的规则把箱子往上堆，求出最高的堆法。
解法：
用DP画表格。
如二维的箱子的堆法:
1.
Max_Box.i = Max ( Max_Box.j ) + 1
a)
for(i = 1 ; i <= 5 ; i++ )
排序後的编号 箱 子 最大高度 先前的箱子
1 2 3 1 Null <-- i == 1
2 2 5 1 Null
3 3 7 1 Null
4 5 6 1 Null
5 7 8 1 Null
b)
排序後的编号 箱 子 最大高度 先前的箱子
1 2 3 1 Null
2 2 5 2 1 <-- i == 2
3 3 7 1 Null
4 5 6 1 Null
5 7 8 1 Null
c)
排序後的编号 箱 子 最大高度 先前的箱子
1 2 3 1 Null
2 2 5 2 1
3 3 7 3 2 <-- i == 3 (检查
1 ~ 2 的箱
子，寻找到3的
时候最大的高度)
4 5 6 1 Null
5 7 8 1 Null
依此类推，建立整个表格。然後找出最大高度，接着依照先前的箱子找出排序规则。因为
答案是要由小排到大的顺序，所以在一开始可以用由大到小来建表，则在回溯解法的时候
就会是由小到大了。如果依照上面的东东的话到时候回溯出来的是由大到小，要输出的话
就要再整理一次。
p.s. 觉得这题用到蛮多排序的，如用C写的话可以参考一下 qsort()的语法，相关说
明可以到linux底下问一下男人(man)
--
※ 发信站: 批踢踢实业坊(ptt.csie.ntu.edu.tw)
◆ From: jul
※ 编辑: aecho 来自: jul (03/21 13:30)
※ 编辑: aecho 来自: jul (03/21 13:43)