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 vvinter at 2010-11-21 23:37:45 on Problem 2336
/*
 * 单次可以运n辆车,单程时间是t,有m辆车,每辆车到达时间为a[i]
 * 
 * 设f[k]为运送第k辆车到达对岸的最短时间,g[k]为最短到达时间为f[k]时的最小来回次数
 * 则f[k] = 第k辆车的到达时间+第k辆车的等待时间+单程时间
 * 问题转化为求第k辆车的最小等待时间
 * 第k辆车的最小等待时间=min{f[k-i]+t>a[k]?f[k-i]+t-a[k]:0}, 其中1<=i<=n
 * g[k]=g[k-i]+1 其中i为求上式时选定
 */

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