Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
一点思路,转的……最佳方案构造法:以下是构造N个人(N≥1)过桥最佳方案的方法: 1) 如果N=1、2,所有人直接过桥。 2) 如果N=3,由最快的人往返一次把其他两人送过河。 3) 如果N≥4,设A、B为走得最快和次快的旅行者,过桥所需时间分别为a、b;而Z、Y为走得最慢和次慢的旅行者,过桥所需时间分别为z、y。那么 当2b>a+y时,使用模式一将Z和Y移动过桥; 当2b<a+y时,使用模式二将Z和Y移动过桥; 当2b=a+y时,使用模式一将Z和Y移动过桥。这样就使问题转变为N-2个旅行者的情形,从而递归解决之。 Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator