急求解两个算法题目

Question

1.N根钢管重量为i,按顺序选择相邻的焊接,价格与两段重量成正比.求最好的代价最小的焊接方法.
2.有N个人在一个水龙头前排队接水,假如每个人接水的时间为Ti,请编程找出这N个人排队的一种顺序,使得N个人的平均等待时间最小.

Answer 1

第1题没看明白
第2题，假设第k个人，那么他的等待时间是前k-1个人的接水时间之和，所以对于每个k，使得sum(t0到tk-1)最小，所以，应该是从小到大排序总时间应该最小
比如2个人，一个人的接水时间是1秒，另一个人的接水时间是2秒，如果1排在2后面，那么总的等待时间为0(第1个人的等待时间，不用等)+1(第2个人的等待时间，是第1个人的接水时间)，如果是2排在1后面，那么总的等待时间就是0(第1个人的等待时间，不用等)+2(第2个人的等待时间，是第1个人的接水时间)，所以，后一种排队比前一种排队所需的时间大

Answer 2

第一个问题是石子归并问题，以前简单研究过，http://topic.csdn.net/u/20110420/00/2945b4af-4681-42c0-9bd1-65a1c3a76f25.html，普通思路是动态规划，优化思路是四边形不等式，如果把模型转化为最优二叉搜索树，则还有n*log(n)的方法。第二个问题就是从小到大排个序。

Answer 3

一开始看第一题没看懂，后看到了ls的石子合并。自愧不如啊~~
 //s[i,j]用来表示合并方法，i表示从编号为i的石头开始合并，j表示从i开始数j堆进行合并，s[i,j]为合并的最优得分。
s[i][j]=max(s[i][j],s[i][k]+s[temp][j-k]+sum[i][j]);ps：你给的四边形不等式(123楼中)不是有三个for嵌套吗？为何复杂度回到O(n^2)？

Answer 4

第一题：Huffman树
第二题：按接水的时间Ti排序

Answer 5

第一题：Huffman树
第二题：按接水的时间Ti排序

Answer 6

这部分是由平摊分析得来的，因为决策点只会向一个方向移动，简单来讲就是n次移动n步，但这n步怎么走是不确定的，有可能每次走1步。也可能某一次走了n步，其他都没有动地方。详细的请搜索一下专业的证明吧，印象中knuth证明过四边形不等式的问题。