新鲜狗狗店面，感觉是跪了啊。。。

zzgzzm 发表于 2016-10-28 09:55
我定义供暖站覆盖范围m是指覆盖m个连续整数[left, left+m-1]。若是指单位区间个数的话类似，不影响算法实现 ...

最小m的上届不应该是ceiling[房子最大间距/(n+1) ]吗？因为这个至少是可以满足条件的

hxtang 发表于 2016-9-1 03:21
第一问greedy第二问递归？

补充内容 (2016-9-1 08:44):

想问下你说的dp的递推公式是啥？

zzgzzm 发表于 2016-10-31 03:24
不是很明白这个DP的意思。dp[j]本身的定义是什么？是指是用i个站来供应前j个房子的每个站的最小m吗？
每 ...

你说的没错，你的例子如果用dp的结果也是0

类似于这道题，只是状态转移方程有区别 http://www.lintcode.com/en/problem/post-office-problem/

wangyiduo999 发表于 2016-10-31 02:39
第二问应该是dp吧
一个维度是供电站的个数i:0->n
一个维度是前j个供电站所需要的覆盖的范围m

说的明确点吧
n = A.size()
开一个dp[m+1][n+1]的数组

dp[i][j]表示有i个供电站前j个房子所需要的最小供暖范围
dp[i][j] = min(max(dp[i-1][k], (A[j] - A[k])/2))
                       k= 0->j;

n^3 的dp

上面的没打完就直接回车了。。。

n = A.size()
开一个dp[m+1][n+1]的数组

dp[i][j]表示有i个供暖站前j个房子所需要的最小供暖范围
dp[i][j] = min(max(dp[i-1][k], (A[j-1] - A[k])/2))
                       k= 0->j-1;

n^3 的dp

wangyiduo999 发表于 2016-10-31 05:38
上面的没打完就直接回车了。。。

n = A.size()

再准确点是mn^2的复杂度，m = 多少供暖站， n = 房子的个数

hxtang 发表于 2016-9-1 03:21
第一问greedy第二问递归？

补充内容 (2016-9-1 08:44):

请问这个题递归是什么思路？小一号的问题是什么？

mingrui 发表于 2016-10-31 04:04
最小m的上届不应该是ceiling[房子最大间距/(n+1) ]吗？因为这个至少是可以满足条件的

哦，你说的对，最小m的上届应该和n有关（我的（房子最大间距+1）太松了，会浪费几次binary search）。
另外这个最小m的上届应该是ceiling(房子最大间距/n)+1吧 （例如用n=1验证）

wangyiduo999 发表于 2016-10-31 05:44
再准确点是mn^2的复杂度，m = 多少供暖站， n = 房子的个数

谢谢，我明白了。是因为一个既然最佳覆盖方案的供暖站之间是不会有重叠覆盖的，所以用i个站盖住j个房子的最佳方案一定是前(i-1)个站盖住了左边的连续某k个房子(0<k<j)，然后最后一个站一定盖住了剩余靠右边的(A.size()-k)个房子。这个时间O(站个数×房子个数^2)，空间最优到O(房子个数)因为dp(i, *)只依赖于dp(i-1, *).
看来你定义的“覆盖”是用覆盖半径的长度，不过这怎么定义不影响实现，而且题目也没有明确说什么是“覆盖范围”。

补充内容 (2016-10-31 09:19):
就是这个算法复杂度比较高

zhengyuyu 发表于 2016-10-31 08:08
请问这个题递归是什么思路？小一号的问题是什么？

第二问可以利用第一问结论进行binary search (24层)，或用DP（35层）。