Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一点思路,转的……

Posted by prowind at 2009-01-06 21:23:36 on Problem 1700
最佳方案构造法:以下是构造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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator