一个dp题# JobHunting - 待字闺中
s*h
1 楼
有一条线段上有点1, 2, 3, ...n, 均匀分布, 每两个之间间隔为1,从一点出发
到另一点需要花费时间t = 1.
假定你从某点s出发, 需要遍历所有的点. 每点i都有一个时间ti与之相关,必须在
ti之前到达点i.
如何在最短时间里面遍历所有的点, 并且满足ti的限制? 提示(可以使用S(i,j,x)表示遍历点i->j, 满足ti,且终止在点x(x = i or j).)
这个好像可以写成
OPT = min(S(1,n,1), S(1,n,n))
S(1,n,n) = min{((S(1,i,i) + (n-i)) > tn) ? inf : keep the value, or
((S(1,i,1) + n) > tn) ? inf: keep the value}
...
但是从1出发就trivial了.出发点不是1, 这个解没有用. 如果i!=1, S(i,j,x)怎么表示呢? 如果写成
S(i,j,j) = min{((S(i,k,k) + (j-k)) > tj) ? inf : keep the value, or
((S(i,k,i) + j) > tj) ? inf: keep the value}
...
这好像和从哪点出发并没关系...提示也没说到从哪儿出发的问题.所以这个提示我还没完全理解.哪位有什么高见?
到另一点需要花费时间t = 1.
假定你从某点s出发, 需要遍历所有的点. 每点i都有一个时间ti与之相关,必须在
ti之前到达点i.
如何在最短时间里面遍历所有的点, 并且满足ti的限制? 提示(可以使用S(i,j,x)表示遍历点i->j, 满足ti,且终止在点x(x = i or j).)
这个好像可以写成
OPT = min(S(1,n,1), S(1,n,n))
S(1,n,n) = min{((S(1,i,i) + (n-i)) > tn) ? inf : keep the value, or
((S(1,i,1) + n) > tn) ? inf: keep the value}
...
但是从1出发就trivial了.出发点不是1, 这个解没有用. 如果i!=1, S(i,j,x)怎么表示呢? 如果写成
S(i,j,j) = min{((S(i,k,k) + (j-k)) > tj) ? inf : keep the value, or
((S(i,k,i) + j) > tj) ? inf: keep the value}
...
这好像和从哪点出发并没关系...提示也没说到从哪儿出发的问题.所以这个提示我还没完全理解.哪位有什么高见?