UC知道一道C编程问题
来源：百度知道 编辑：UC知道 时间：2024/05/21 12:59:59
语言：C
巴比伦人有N种石块，每种石块的数量均为无限。石块是长方体，每种石块的三维分别为xi,yi,zi。石块可以任意转动。巴比伦人想用这些石块造出一个尽可能高的塔。当然，不是说石块数量无限塔的高度也就无限了，塔的建造是要符合自然规律的――放在上面的石块的地面的两维必须分别严格小于放在下面的石块的底面两维。严格小于就是指不能相等。比如，一个底面为3×3的石块不能放在底面为3×3、2×4、1×2的石块上面，但是能放在底面为4×5的石块上面。也就是说，同样类型的石块如果不进行旋转是没办法叠起来的。
输入格式：
输入包含多组数据，每组数据相互独立。对于每组数据，第一行有一个整数N（N <= 30），表示有N种石块。接下来的n行，每行三个空格分隔的整数，描述每个石块的三维xi、yi、zi。最后一组数据N为0，表示整个输入结束。该组数据不需要被处理。
输出格式：
对于每组数据，输出仅一行，上面一个整数，表示巴比伦之塔最高能造多少高。
样例输入：
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
0
样例输出：
28
测试数据：
6
31407 24166 13404
25563 24835 31354
921 10445 24804
7963 19319 1423
31328 10458 1946
14480 29984 18752
7
3895 18671 8260
16249 7758 15630
13307 28607 13991
11739 12517 1415
5263 17117 22826
3182 13135 25344
8023 11234 7537
30
1767 15207 23932
5191 21886 4311
27810 4348 8302
这是个有点麻烦的动态规划问题
首先给每块砖的长宽高都排个序，使得xi>=yi>=zi，省得之后还要写一大堆if
假设最底下的砖的底面的长和宽分别为a和b(a>=b)的时候，所能够搭出的石塔的最大高度为f(a,b)
那么可以得到状态转移方程
f(a,b)=max
{0,
f(xi,yi)+zi(xi<a && yi<b时)
f(yi,zi)+xi(yi<a && zi<b时)
f(xi,zi)+yi(xi<a && zi<b时)}(1<=i<=n)，转移时间代价为O(n)
最后求出f(无穷大,无穷大)(表示最底下的是地面)即可
但是这样的方程有个问题，就是xi yi zi的值可能会很大，导致a b很大，因而开不出那么大的数组
而且，在一种推广了的情况中，如果砖的棱长不是整数，这样的算法就失效了
因此必须做以下改进措施
注意到n<=30，因此不同的棱长总共只有3n=90种，只要记录下所有的棱长在一个数组int L[]中，然后将数组L排序并清除重复的棱长，然后修改每块砖的信息，将砖的每条棱长记录成该条棱在L数组中的下标即可（这种操作通常被称之为“离散化”）
比如有两块砖(x1=1,y1=2,z1=3)和(x2=100,y2=200,z2=1)，那么得到的L数组就是{1,2,3,100,200}，然后两块砖的信息就成了(x1=0,y1=1,z1=2)和(x2=3,y2=4,z2=0)
然后，令F(i,j)(i>=j)表示最底下的砖的长和宽分别是L[i]与L[j]时，石塔的最大高度
就有状态转移方程
F(i,j)=max
{0,
F(xk,yk)+L[zk](xk<i && yk<j时)
F(yk,zk)+L[xk](yk<i && zk<j时)
F(xk,zk)+L[yk](xk<i && zk<j时)}(1<=k<=n)，转移时间依然是为O(n)
令m表示数组L的元素个数，然后增设一个L[m]=无穷大，