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 fresh732 at 2012-11-24 19:31:57 on Problem 1695
这个题我参考了别人的解题报告,题目很容易让人产生误解,其实不用去求最短路,求了反而不对,
直接用输入中所给的两点间的距离就行了。方法是三维DP。f[a][b][c]表示当前离起点最远的车处在
c位置,另外两车分别处在a,b位置时的所需要的最少的投递时间。那么下一个状态只有三种可能,即
f[a][b][c+1],即c车到了c+1处
f[a][c][c+1],即b车到了c+1处
f[b][c][c+1],即a车到了c+1处
当c==(目标点时) 结束。
采取记忆化搜索的方式。

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