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

dp,,额,,,,,,,,,,

Posted by yy17yy at 2010-12-23 11:27:15 on Problem 3377
for(i=y1+1;i<=y2;i++)
		{
			__int64 temp=dpa;
			dpa=min(dpa+a[i],dpb+b[i]+c[i]);
			dpb=min(dpb+b[i],temp+a[i]+c[i]);
		}
dpa->到河上点的最短路,,dpb->到河下点的最短路,,
y1->起点,,y2->终点;
a[i]->河上之间的时间,,b[i],,河下之间的时间,,,c[i]上下之间的时间....
dp之前需要修改c[y1]和c[y2],,,方法是向两边遍历寻找过河最小的时间..因为这个过程只可能
过一次河,,所以很好找,,,,

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