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 forgotten at 2007-03-30 23:08:08
In Reply To:排了一下版……有想法的在这里回或者PM我吧,谢了~~ Posted by:forgotten at 2007-03-30 22:06:00
对于第一题
f[i][time][set],剩下time时间,遍历点集为set,遍历序列的最后一个点为i,达到这样的状态最少费用是多少。
扩展成
1. j不在set中,f[j][time-dist[i][j]-value[j]][set+[j]] + cost[i][j]
2. j在set中,f[j][time-dist[i][j]][set] + cost[i][j]
DP完后
再枚举两次遍历的点集各是什么
因为两次遍历的点集的交集没有要求一定为空,所以必须枚举两次,这样时间复杂度就高了。

那单就DP的方法来说,对了么?

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