1.正确的算法: 
如果n=3, 过河时间为A+B+C 
如果n<=2, 好算, 不费口舌了 

如果n>=4, 这个是重点: 
每次优先考虑把最慢两人送过河 
把n人中最快两人记为A,B, 最慢两人记为C,D(过河时间A<B<C<D), n人问题实质上转换为4人过河问题, 参考到4人过河时的优化, 
记AB过河, A回, CD过河, B回, 为方法X, 实质是利用最快两人进行优化, 耗时A+2B+D 
记AD过河, A回, AC过河, A回, 为方法y, 实质是利用最快一人来过河, 耗时2A+C+D 
每次比较这两个方法, 如果x快, 使用x方法, 如果y快, 则用y, 并且, 一旦某次使用y方法后, 以后都不用比较了, 全部使用y方法过河 

2.算法正确性证明: 
为什么每次先让最慢两人过河? 因为他们迟早要过河...早过晚过一样, 而晚过的话, 有可能时间不能被优化, 所以选择最先过 

为什么某次用y过河后不用再比较xy了? 

y比x快的原因是2A+C+D < A+2B+D, 即 A+C<2B 
容易想到, 从此以后A+C都会小于2B了(因为C越来越小)

代码自己想吧，写了没意思了

• Re:其实是这样 (33) tzkq 2010-02-19 17:22:15
• Re:其实是这样 (566) forgetEver 2012-06-28 20:56:44