Question

一道很难的题。。没有想明白，希望高手帮我 !!

我假设有A B C D 四种房子，每种房子分别有1W 2W 3W 4W的价值。A可以随便建造，B必须建在A的旁边，C必须建在B A的旁边，D必须建在A B C 的旁边。现在有一个5×5正方形25个格子的面积（一个格子是一个建造单位，可以在上面建造一所房子）。问怎样建造才能获取最大的价值？

PS:本人不经常提问，而且我还有900多分可以用。所以对于悬赏金不是很吝啬。希望高手明白后详尽解答一下，我会追加100分的！！！我注重的只是这道题的解法，虽然最后可能没有人能打出来，但是我不会辜负解答最详尽的人的~
额。。。做一下修改啊~是与所要求的房子相邻，比如D必须与A B C 相邻

呵呵，对了。就是诺基亚上面的一个游戏。但是我对这道题更有兴趣~
我自己试出来的是58，但是有位朋友答出来60，而且似乎是正确的。。。我希望有哪位高手可以给出一个确定的正确答案，并且有清晰正确的解题过程~
先在此谢过了~！！！
呵呵，也谢谢各位帮忙做题~

所有的回报，都是在付出的前提下给予的，但是反过来，寒酸的付出并不见得会有回报。有些朋友的确给出了很强的理论，但是答案让你们的话站不住脚。所以，答案 推理过程，这两者请各位高手都给出来.

很感激有位朋友给出的类似题目的链接，但是那个答案是不对的~第四行的第一个绿房子周围没有蓝房子~

像这种由游戏引申来的问题。。。除了专业人员，对我们来说本来就无所谓有无答案一说。。大家能够有说服人的推理过程就行（最起码你推论得出的答案要看上去对啊。。。这些话非要我说出来才知道么。。。。。。）

Answer 1

楼主所说的“D必须建在A B C 的旁边”不知道在ABCD组成四方形时是否成立？即对角是否在“旁边”的范围？
看了补充，应该是不包括上面说的情况，那么个人思路如下，供参考：

设ABCD四种元素的个数分别为abcd，则a+b+c+d=25；设每个格的均值为R，单元个数为T。
将ABCD看成有四个方向的元素，分别有0到3个方向的约束，
A最多可从4个方向约束BCD，即4a>a+b+c
B最多可从3个方向约束CD（自身1个方向受A约束），即3b>c+d
C最多可从2个方向约束D（自身2个方向受AB约束），即2c>d

依题意，ABCD四种元素的组合方式如下：
●看含一个各种元素，不完备的最小单元：
①□A□ 占用1个格，均值为：1/1；
②□AB□ 占用2个格，均值为：(1+2)/2=1.5
③□ACB□ 占用3个格，均值为：(1+2+3)/3=2
④□C□□
□A D B□ 占用4个格，均值为：(1+2+3+4)/4=2.5
●再看含一个各种元素，且完备的最小单元：
①□A□ 占用1个格，均值为：1/1；
②□AB□ 占用2个格，均值为：(1+2)/2=1.5
③□ACBA□ 占用4个格，均值为：(1+2+3+1)/4=7/4
④□BCA□
□□ADB□ 占用6个格，均值为：(1+1+2+2+3+4)/6=13/6
（含1个C或D的完备单元还有其他组合，但占用格数都比上面的多，R也比较小）
由以上可知，所有最小单元中，不完备的Rd均值最大！
一个完备的5阶(5×5)的单元，是由所有完备或不完备的独立单元组成，
因此其均值R(5×5)<Rd=2.5。
因此，其和T(5×5)<2.5×25=62.5

●再关注下跟最值关系紧密的D，它最大的共用约束：

以上3种情况分别为两个D共用BC、AC、AB时的最小完备单元，其中以共用BC时，一个D平均占用格数最少（9/2=4.5格）；
所以，构建1个ABCD的完备单元，其平均占用格数不可能小于1个不完备的D单元占用的格数(4格)，所以在5阶(5×5)的单元，d<25/4，因此d可能的最大值为6！

这里不好说明，看空间图片：http://hi.baidu.com/abei%5F945/blog

Answer 2

应该从最低廉的房子造起。

第一步：造A类房，用最少的A房，而使所有的空地都有A房相邻；
第二步：造B类房，用最少的B房，而使所有的空地都有B房相邻；
第三步：造C类房，用最少的C房，而使所有的空地都有C房相邻；
第四步：造D类房，把所有的空地都造上D类房。

第一步的解数，所有通过旋转、反射变换可以互相转化的解当作同解，应该不多，每一种解称为一个局面。然后基于每一局面进行下一步，直到完成第三步。所有分枝都列出后，就能比较出最大解。
-----------------------------------------------------------------10-19 21:38
用这个方法可以证明解的最大性.等我整理好了贴出来.

Answer 3

BABDA=10
CADCB=13
DBDAC=14
ADCBD=14
BCACA=10
10+13+14+14+10=61

暂时是最高的了吧....
我到现在还没想出来有什么方法能证明这个就是最高的
我只把我的做法说一遍
要是以后能证出来再告诉你

首先知道D的价值最高
那么就应该尽量多的造D(这句话并不严密,但实践中还没发现错误)

我用图形来说明步骤
字母表示前面步骤确定的数,数字表示此步骤加上去的数
因为这里只支持打一个空格,所以"?"表示空格

第一步
4

第二步
2
1D3

第三步
B41
ADC

第四步
BDA
ADC
241
3
这一步我认为是关键,因为我尝试这把两个D造在一起

前四步还是蛮有条理的,下面的步骤就有点想当然了

第五步(随便找了个位子写了个D)
? BDA
ADC
4BDA
? C

第六步(把D周围补全)
21BDA
3ADC
DBDA
1 C

第七步(理所当然第四行第2格应该是D)
BABDA
CADC
DBDA
A4C

第八步(补上两个B)
BABDA
CADC2
DBDA
ADC
2

第九步(一个接一个按要求补完)
BABDA
CADCB
DBDA3
ADC24
B3131

结束,希望对LZ有帮助

Answer 4

我排出来的一种方法，总价值66W：

D A D A D =14
B C B C B =12
D A D A D =14
B C B C B =12
D A D A D =14

Answer 5

首先,结果要用最多的D,A的使用率最频繁,那就提高A的利用率,同时加强B和C的利用率.最理想的情况就是如下图1
D B D
C A C
D B D
D有4个，A一个，BC等同均为2个
然后我们分析5X5的格子,如图2
1 2 2 2 1
2 3 3 3 2
2 3 3 3 2
2 3 3 3 2
1 2 2 2 1
如上图我对25个格子分成了3类,分别边、角、中间，其中编号为1的只与周围3个格子相连接(利用率最底,而且可满足D的条件),编号为2的格子与5个格子相连接,而编号为3的格子与周围8个格子相连接,分析完之后,我们得出A必须放在3类格子上,而1类格子可都放D.这样才能保证A的高利用率，那么先把D放到位置1上去，可得下图3
D 2 2 2 D
2 3 3 3 2
2 3 3 3 2
2 3 3 3 2
D 2 2 2 D
然后根据D的放置条件，再反推ABC的位置，加上位置3要放A可以确定，那么就看BC的位置，对于5X5属于对称表格，与D想连的两个位置2效果等同，随意可先随意放BC，最后根据整理利用情况调整BC。然后得下图4
D B 2 B D
C A 3 A C
2 3 3 3 2
C A 3 A C
D B 2 B D
然后我们看图1，其实，5X5的格子可划为4个图1的样子，把中间的数字组成“十”字架当成分割线，如图5
D B 2 B D
C A 3 A C
2-3-3-3-2
C A 3 A C
D B 2 B D
这样就可以按图1把其他的位置补齐，可得图6
D B D B D
C A C A C
D B D B D
C A C A C
D B D B D
完成，计算总价值
4+2+4+2+4=16
3+1+3+1+3=11
4+2+4+2+4=16
3+1+3+1+3=11
4+2+4+2+4=16
总16+11+16+11+16=70
那么。最多可得70个价值~~~~

呵呵，不知道你看懂没~~~~
另外这个好象在老婆手机游戏上面有个类似的建筑游戏，也是这样，诺基亚的手机，盖楼的，不知道楼主是不是哪个问题引申的啊 ！~~~~

Answer 6

A D C B A=11
D B A C D=14
C B A D B=12
A D B C A=11
B C A D B=12
11+14+12+11+12=60
其中有7个A，7个B，5个C，6个D，而7+7+5+6=25，
又因为D的价值最高，所以D越多越好，
然而从7+7+5+6=25来看，6个D已经是D最多的排列方法了。
所以以上的排列的最大的价值为60。
但是我觉得还有一种就是其中有7个A，6个B，6个C，6个D，而7+6+6+6=25，
这加起来就有61W了，但是我却想不出来。。。
既然楼下的有人想出来了，那我就用了。。。
B A B D A 10
C A D C B 13
D B D A C 14
A D C B D 14
B C A C A 10
10+13+14+14+10=61
其中有7个A，6个B，6个C，6个D，而7+6+6+6=25，
然而从7+6+6+6=25来看，6个D已经是D最多的排列方法了。
所以以上的排列的最大的价值为61。
从以上所有的排列来看，A的个数≤B的个数≤C的个数≤D的个数 。。。
然而是否存在，两个D公用一个C、B、A，或两个C公用一个B、A，或两个B公用一个A 。。。
这个问题暂时还是没有提出来的，我提议楼主去编个程序来做这道题。
先确定是否存在上面公用的情况，然后在去证明。。。 （仅供参考）
一切的一切，只是为了楼主的200分。。。