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 grapland at 2010-02-08 13:59:57 on Problem 3411
设状态state为每个含优惠条件(Ci)或为终点的节点是否被遍历过(即1&(state>>i)==1 当且仅当i点为优惠点或终点且被遍历过),且opt[state][i]为当状态为state,车在i点时从原点到i点的最小费用(最短路)。
转移:opt[ns][i]=min(opt[ns][i],opt[ps][j]+SP(j,i));
这里,SP(j,i)为从ps转移到ns过程中,在ps决定的图中,从j到i的最小费用(最短路).
从ps更新每个ns时,i取所有在ps中不存在,在ns中存在的节点,j取所有在ps中的节点,且j!=i.
ns和ps只允许有一位不同.

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