marvel真有钱啊 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Movie - 无限影话

marvel真有钱啊

marvel真有钱啊# Movie - 无限影话

K*g2014-09-24 07:09

1 楼

write a program for placing of n hospitals, in M cities,distance between the
cities should be minimum. write the recursive expression.
Assuming nthis set you have to find set of n cities which have minimum distance.
看上去像DP，但是好像subproblem的解不是更大一个subproblem的解，请大家讨论下

k*r2014-09-24 07:09

2 楼

想查个演员，结果发现。
http://www.imdb.com/title/tt2015381/

B*t2014-09-24 07:09

3 楼

f(i, j) = min(f(k,j-1)+g(k+1, i)) j-1<=kf(i,j): put j hospitals in the first i cities.
g(a,b): put 1 hospital between cities a and b
O(M^2*N), maybe it can be optimized to O(M*N), but need proof.

K*S2014-09-24 07:09

4 楼

that's why Disney's stock is hot. Disney also bought star wars.

【在 k***r 的大作中提到】

: 想查个演员，结果发现。
: http://www.imdb.com/title/tt2015381/

K*g2014-09-24 07:09

5 楼

看不懂？能详细点吗？
从M个city里取k个使得所有的距离最短，从M个city里去K-1个使得所有的距离最短，很
显然，后者的解不一定在前者里。好像不符合DP的条件

【在 B*****t 的大作中提到】

: f(i, j) = min(f(k,j-1)+g(k+1, i)) j-1<=k: f(i,j): put j hospitals in the first i cities.
: g(a,b): put 1 hospital between cities a and b
: O(M^2*N), maybe it can be optimized to O(M*N), but need proof.

k*l2014-09-24 07:09

6 楼

star what?

【在 K******S 的大作中提到】

: that's why Disney's stock is hot. Disney also bought star wars.

B*t2014-09-24 07:09

7 楼

上面给出的是假定M个city在一条直线上的结果。
如果M个city不在一条直线上，感觉是个NPC问题，估计要先用Floyd求出all pairs
of shortest path。

很

【在 K******g 的大作中提到】

: 看不懂？能详细点吗？
: 从M个city里取k个使得所有的距离最短，从M个city里去K-1个使得所有的距离最短，很
: 显然，后者的解不一定在前者里。好像不符合DP的条件

k*r2014-09-24 07:09

8 楼

突然发现昨晚在家里用chrome浏览的和今天上班用火狐看到的不一样啊，广告期结束了
还是chrome有特殊照顾？

g*u2014-09-24 07:09

9 楼

能解释下什么是“set of n cities which have minimum distance”？是两两距离之
和最短吗？如果是，可以这样做：
D(i,j):用前i个城市选j个的最短距离
d_k,l: 城市k,l之间的距离
D(i,i): 全选的两两距离之和
D(i,j) 两种情况
1）选i:D(i-1,j-1)+(sum of d_j,k), k是那j-1个城市任一个。
2）不选i: D(i-1,j)
取 min{1),2)}
time&space O(n^3)

the

【在 K******g 的大作中提到】

: write a program for placing of n hospitals, in M cities,distance between the
: cities should be minimum. write the recursive expression.
: Assuming n: this set you have to find set of n cities which have minimum distance.
: 看上去像DP，但是好像subproblem的解不是更大一个subproblem的解，请大家讨论下

k*52014-09-24 07:09

10 楼

那叫Lucas film

【在 k**l 的大作中提到】

: star what?

K*g2014-09-24 07:09

11 楼

好像有道理。但是你怎么确定边界条件呢？例如
D（1，1）=0
D(2,1)=0 D(2,2)=a
D(3,1)=0, D(3,2)怎么求呢？

【在 g*****u 的大作中提到】

: 能解释下什么是“set of n cities which have minimum distance”？是两两距离之
: 和最短吗？如果是，可以这样做：
: D(i,j):用前i个城市选j个的最短距离
: d_k,l: 城市k,l之间的距离
: D(i,i): 全选的两两距离之和
: D(i,j) 两种情况
: 1）选i:D(i-1,j-1)+(sum of d_j,k), k是那j-1个城市任一个。
: 2）不选i: D(i-1,j)
: 取 min{1),2)}
: time&space O(n^3)