Detail of message

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

Re:状态DP做法

Posted by BigFoot2014 at 2015-10-11 12:36:49 on Problem 3411
In Reply To:状态DP做法 Posted by:grapland at 2010-02-08 13:59:57

> 设状态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:

Re:状态DP做法 (2) BigFoot2014 2015-10-11 12:37:05

Post your reply here:

Home Page Go Back To top