| ||||||||||
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 |
这样做对么?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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator