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 |
帮助这个题我参考了别人的解题报告,题目很容易让人产生误解,其实不用去求最短路,求了反而不对, 直接用输入中所给的两点间的距离就行了。方法是三维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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator