帮转:
在做Mathworld OA遇到的題目，想了很久還是解不出來，有人可以提供思路嗎？
input row, col, 成為矩陣，還有興建的building n, building n 擺進矩陣後，求building之間最大的距離，到邊界也算
是leetcode 317的变形题。
1 Like
我看那个截图的意思是，在 w × h 的场地上 修建 n个office，其他区域为parking lot，返回值为最远的停车场到office的距离。不是下面说的“求building之間最大的距離”
图里的0，1，2各表示什么啊
0表示那个格子是一个office building， 其他数字的格子都是parking lot，1就表示那个parking lot距离最近的office的距离是1
我认为，DP的话，主要是怎么递归。
比如，上面的样例是放3个office，然后填入所有的最近数字以后，得到
1 0 1 2
2 1 2 1
1 0 1 0
2 1 2 1
这个情形，如果我们从第一行分割，会得到两个图形
1 0 1 2， 它是 1×4的矩阵中填1个数的情形
和
2 1 2 1
1 0 1 0
2 1 2 1
它是3×4的矩阵中填2个数的情形
分割以后，图中填的数字没有发生变化，所以
f(4,4,3) = max(f(1,4,1), f(3,4,2))
这个可以递归。
问题是，能否证明，最优解一定可以分割成两部分，分割后数字不发生变化
office的位置没有给对吧？
这样就是要优化office的位置先
对的，随便选office的位置
也许思路应该是找到office的最佳位置，然后最远距离自然解决了
感觉有点exam room的二维版本
有道理，我再想想
感觉放的位置greedy是可行的
不明白，用什么规则greedy
比如一维的情况，那肯定是均分嘛
二维就复杂多了，需要保证另外一个维度，奇偶数还要区分。其实如果你定义一种策略去放，只要这种策略work，就是正解。
嗯，可以，只是策略有点难想
偶数很简单吧