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

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/

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

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):

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

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

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