【挑战】批处理实现最大长方体问题、四色定理问题、导弹拦截问题

yslyxqysl

1.最大长方体问题
有一个文本a.txt，里面有n(不定)个n*n的矩阵，
矩阵之间用“#层数”分开，
这些矩阵代表一个n*n*n的正方体，
正方体中的每一个1*1*1的单位上都标有一个数字，例如：
示例：

#1
-1 3 -2
8 -2 2
0 -4 -4
#2
2 15 7
12 5 2
-1 0 10
#3
-4 -4 -4
-2 3 -1
-128 -13 3

这就代表一个正方体，其中
(1,2,3)是-4(第一个，第二行，第三层)，
(3,2,1)是2(第三个，第二行，第一层)。

现在要从这个正方体中“切”出一个长方体，
使得这个长方体中所有数的和最大。
当有多个答案时取体积最大(数的个数最多)的那个
要求输出数的和以及数的个数。

例子的答案（可能是吧）：
52
18

参考分数：满分70分，2技术，1声望。

2.四色定理问题
A公司要给一幅很大的图涂上颜色，要用四种颜色把n(不定)块图案分开
他们给你这个计算机专家一个文本pic.txt，示例如下：
# 1 2 3 4 5 6 7 8
1
2 1
3 0 1
4 0 0 1
5 0 1 0 1
6 0 0 0 1 0
7 0 0 0 0 1 1
8 1 1 0 0 0 0 1
这个文本说明了块与块之间是有边相连(1)还是无边相连(0)
例如(2,5)的值为1，就说明2和5是有边相连的；
(4,7)的值为0，就说明4和7是无边相连的。
请注意，图案中的块的个数是不定的，
可能8块也可能更多或更少。

试输出一种涂色方案，今假设用红黄蓝绿四种颜色。
例子的其中一种答案：
1:red
2:yellow
3:red
4:yellow
5:green
6:green
7:blue
8:green

实际图形（一种可能的情况）


参考分数：满分50分，1技术。

3.导弹拦截问题
Y国自主研发了一套导弹拦截系统，可惜这套系统有一个缺点，
就是一套系统发射了一枚拦截导弹后就会产生磨损，下一发
拦截导弹就不能比前一发射得高或和前一发一样高了。
不巧Y国只完成一套系统之后，就与X国发生了战争，
X国陆续投来一些(不定)不同高度的导弹，试问Y国仅有的一套拦截系统最
多能拦住几枚导弹？假设每一枚拦截导弹都能准确击中目标。

示例输入：
10 7 8 3 7 4 2 11 9

示例输出：
5

参考分数：满分30分。

[ 本帖最后由 yslyxqysl 于 2009-10-31 07:13 编辑 ]

yslyxqysl

全部是Pascal书(来自我们学校图书馆)上的BT题...