j**l
发帖数: 2911 | 1 一个俄国人问的题，估计要是fail的话就是栽在这道题目上了。
这题从Goolge的那个百层楼扔鸡蛋题变换而来，原来那道题，只需要从14, 27, 39, 50,
60, 69, 77, 84, 90, 95, 99依次扔第一个鸡蛋就可以了，然后再用第二个鸡蛋线性探测
变体题是这样的，从A地发货到B地，所需要时间是某个常数x, 1 <= x <= 100, 怎么找
出x？
方法是寄东西给顾客，顾客的数量不限制．对每个顾客都承诺一个到达天数t, 如果按
时或者提前收到了，顾客就默认了．如果迟到了，该顾客就一定会在t+1天投诉。
现在要求你用这个方法求出x的准确值, 使得等待天数最短（用最短时间得到x), 要求
最多只能收到两次投诉，收到第三次投诉是不行的。
我明确告诉他，这题和一道经典的扔鸡蛋题类似，大体思路就是用第一次投诉机会确定一个范围，然后再收到投诉后改用线性探测。
他说这题是和那题类似，但是要求不同，所以更难。主要是要求等待天数要尽可能短。所以一开始选50天，不是最好的解法。他还说，这题难，主要是看看你有什么思路想法，不要求一定要给出正确的答案来。
他还说，如果一开始太激进，从比 | K******g
发帖数: 1870 | 2 麻烦你把google 那题也详细的写一下吧。多谢了
,
探测
【在 j**l 的大作中提到】
: 一个俄国人问的题，估计要是fail的话就是栽在这道题目上了。
: 这题从Goolge的那个百层楼扔鸡蛋题变换而来，原来那道题，只需要从14, 27, 39, 50,
: 60, 69, 77, 84, 90, 95, 99依次扔第一个鸡蛋就可以了，然后再用第二个鸡蛋线性探测
: 变体题是这样的，从A地发货到B地，所需要时间是某个常数x, 1 <= x <= 100, 怎么找
: 出x？
: 方法是寄东西给顾客，顾客的数量不限制．对每个顾客都承诺一个到达天数t, 如果按
: 时或者提前收到了，顾客就默认了．如果迟到了，该顾客就一定会在t+1天投诉。
: 现在要求你用这个方法求出x的准确值, 使得等待天数最短（用最短时间得到x), 要求
: 最多只能收到两次投诉，收到第三次投诉是不行的。
: 我明确告诉他，这题和一道经典的扔鸡蛋题类似，大体思路就是用第一次投诉机会确定一个范围，然后再收到投诉后改用线性探测。
| j**l
发帖数: 2911 | 3 说说我事后诸葛亮想到的思路吧，面试45分钟想到太难了，就算知道原型的扔鸡蛋题也没有用，而且原型题也不是第一次见到就容易想到的。。。
不妨简化问题便于讨论，设要求的整常数x位于区间[1, 20]之间。
首先，20是不用测的，如果测19的时候收到complain, 则20即所求。
其次，如果不幸收到一个complain, 就好比摔碎了一个鸡蛋，接下来就必须用最慢的线
性探测了。
第一个探测的天数是多少呢？我们先来看看16。
假如探测16收到了complain, 那么我们最坏可能必须线性探测19, 18, 17, 那么总探测
天数是
19 + 18 + 17 + 16 = 70
假如探测16没有complain, 下一个探测的天数是多少呢？
注意到
16 + 15 + 14 + 13 + 12 = 70 <= 70, 再加11就超出
因此我们可以接着探测12
假如探测12收到了complain, 那么最坏可能总探测天数还是70
假如探测12没有complain, 下一个探测的天数是多少呢？
注意到
16 + 12 + 11 + 10 + 9 + 8 = 66 <= 70, 再加7就超出
因此 | j**l
发帖数: 2911 | 4 100层楼，两个鸡蛋，探测哪层楼摔下鸡蛋仍然不破，而再上一层摔就破。
保证存在n, 1<= n <= 100, 当从n层以及n层以下扔鸡蛋不会破，而从n+1层扔鸡蛋就破
原理，先用第一个鸡蛋确定一个大的范围，再用第二个鸡蛋在这范围内线性探测
答案：
依次从14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99，100层扔第一个鸡蛋，如果摔
碎则线性探测，最坏情况都只需要扔14次
【在 K******g 的大作中提到】
: 麻烦你把google 那题也详细的写一下吧。多谢了
:
: ,
: 探测
| b********h
发帖数: 119 | 5 扔14次不是要用14个鸡蛋了吗？直接用binary search不是更快，log（100），7次就可
以了。
【在 j**l 的大作中提到】
: 100层楼，两个鸡蛋，探测哪层楼摔下鸡蛋仍然不破，而再上一层摔就破。
: 保证存在n, 1<= n <= 100, 当从n层以及n层以下扔鸡蛋不会破，而从n+1层扔鸡蛋就破
: 原理，先用第一个鸡蛋确定一个大的范围，再用第二个鸡蛋在这范围内线性探测
: 答案：
: 依次从14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99，100层扔第一个鸡蛋，如果摔
: 碎则线性探测，最坏情况都只需要扔14次
| l*y
发帖数: 21010 | 6 你只有两个鸡蛋，没法用binary search
【在 b********h 的大作中提到】
: 扔14次不是要用14个鸡蛋了吗？直接用binary search不是更快，log（100），7次就可
: 以了。
| j**l
发帖数: 2911 | 7 第一个鸡蛋如果没有扔坏，可以接着再扔
【在 b********h 的大作中提到】
: 扔14次不是要用14个鸡蛋了吗？直接用binary search不是更快，log（100），7次就可
: 以了。
| O*******r
发帖数: 753 | 8 ....
【在 j**l 的大作中提到】
: 第一个鸡蛋如果没有扔坏，可以接着再扔
| K******g
发帖数: 1870 | 9 同意，用Binary search更快.其实就是在一个0/1的有序数组里,找第一个出现的1. O(
logN),但是最坏的情况还是O(N).两题都可以用这种方法解决。比较经典，呵呵。
【在 b********h 的大作中提到】
: 扔14次不是要用14个鸡蛋了吗？直接用binary search不是更快，log（100），7次就可
: 以了。
| j**l
发帖数: 2911 | 10 只有两个鸡蛋可以扔，还要保证最坏情况下扔的次数最少。
这变体题是最多只能收到两次投诉，还要保证最坏情况下探测等待的总天数最小
【在 K******g 的大作中提到】
: 同意，用Binary search更快.其实就是在一个0/1的有序数组里,找第一个出现的1. O(
: logN),但是最坏的情况还是O(N).两题都可以用这种方法解决。比较经典，呵呵。
| | | K******g
发帖数: 1870 | 11 不管怎么样，两个鸡蛋不够啊。
我觉得题目可能是说，让使用的鸡蛋数量最少吧。
谁有这题的原题？
【在 j**l 的大作中提到】
: 第一个鸡蛋如果没有扔坏，可以接着再扔
| l*y
发帖数: 21010 | 12 你好好看看题吧
【在 K******g 的大作中提到】
: 不管怎么样，两个鸡蛋不够啊。
: 我觉得题目可能是说，让使用的鸡蛋数量最少吧。
: 谁有这题的原题？
| i*****e
发帖数: 5233 | 13 你看看原题目吧
【在 K******g 的大作中提到】
: 不管怎么样，两个鸡蛋不够啊。
: 我觉得题目可能是说，让使用的鸡蛋数量最少吧。
: 谁有这题的原题？
| Z*****Z
发帖数: 723 | 14 顺便问一下关于这个扔鸡蛋问题的解析解的理解。
假设允许drop次数为d，允许break鸡蛋个数为b，可以测得最大楼层为f（d，b）
那么f（d，b）= C(d, 1) + C(d, 2) + ... + C(d,b)
这个怎么理解？
【在 j**l 的大作中提到】
: 100层楼，两个鸡蛋，探测哪层楼摔下鸡蛋仍然不破，而再上一层摔就破。
: 保证存在n, 1<= n <= 100, 当从n层以及n层以下扔鸡蛋不会破，而从n+1层扔鸡蛋就破
: 原理，先用第一个鸡蛋确定一个大的范围，再用第二个鸡蛋在这范围内线性探测
: 答案：
: 依次从14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99，100层扔第一个鸡蛋，如果摔
: 碎则线性探测，最坏情况都只需要扔14次
| B*****p
发帖数: 339 | 15 不用一个一个测
如果16收到complain,测18,如果complain, x = 17, otherwise, 测20
也没有用，而且原型题也不是第一次
见到就容易想到的。。。
【在 j**l 的大作中提到】
: 说说我事后诸葛亮想到的思路吧，面试45分钟想到太难了，就算知道原型的扔鸡蛋题也没有用，而且原型题也不是第一次见到就容易想到的。。。
: 不妨简化问题便于讨论，设要求的整常数x位于区间[1, 20]之间。
: 首先，20是不用测的，如果测19的时候收到complain, 则20即所求。
: 其次，如果不幸收到一个complain, 就好比摔碎了一个鸡蛋，接下来就必须用最慢的线
: 性探测了。
: 第一个探测的天数是多少呢？我们先来看看16。
: 假如探测16收到了complain, 那么我们最坏可能必须线性探测19, 18, 17, 那么总探测
: 天数是
: 19 + 18 + 17 + 16 = 70
: 假如探测16没有complain, 下一个探测的天数是多少呢？
| y*c
发帖数: 904 | 16 明确题意+提供思路，假设第一次探测x
则如果x就complain的总天数 x + \sum_{i=x+1}^{i=99}
如果没有complain, 下一次探测总天数 x' + \sum_{i=x'+1}^{i=x-1}
如此下去得到x序列。
很明显，x 应该是比较接近100的一个数，x'是小于x的一个数。原则是希望每一轮总天
数接近。由于第二个“鸡蛋”的测试带来的是平方项，所以第一个鸡蛋测试的gap肯定
不是线性递减的。具体怎么算我还没什么办法。 | j**l
发帖数: 2911 | 17 首先测20是无效测试，它总是不会收到complain的
按照你的说法，如果16收到complain, 测18,
如果有complain, 需要测x = 19来确定x是19还是20，如果测19有complain, 那么你就
有三次complain, 算失败
如果没有complain, 需要测x = 17来确定x是17还是18
【在 B*****p 的大作中提到】
: 不用一个一个测
: 如果16收到complain,测18,如果complain, x = 17, otherwise, 测20
:
: 也没有用，而且原型题也不是第一次
: 见到就容易想到的。。。
| j**l
发帖数: 2911 | 18 在1 <= x <= 20的范围内，我觉得第一次测16是最好的，有complain则线性测19, 18,
17, 在没有complain的情况下接下来依次测12，8，1, 这样能够保证最怀情况下最多等
70天，
19 + 18 + 17 + (16) = 70, 假如第一次测16就收到第一次complain
(16) + 15 + 14 + 13 + (12) = 70, 假如第二次测12的时候才收到第一次complain
(16) + (12) + 11 + 10 + 9 + (8) = 66, 假如第三次测8的时候才收到第一次
complain
(16) + (12) + (8) + 7 + 6 + 5 + 4 + 3 + 2 + (1) = 64, 假如第四次测1的时候才
收到第一次complain
原型题得到的非等差数列，公差依次减少1，能够保证数列到达100层，还能使最坏情况
下，都只需要扔14次。
两题的相似处，都有一系列的插入点，一个是扔第一个鸡蛋的楼层14, 27, 39, 50...,
另一个则是没有收到第一次complain前的一系列探测天数点，比如16, 12,
【在 y*c 的大作中提到】
: 明确题意+提供思路，假设第一次探测x
: 则如果x就complain的总天数 x + \sum_{i=x+1}^{i=99}
: 如果没有complain, 下一次探测总天数 x' + \sum_{i=x'+1}^{i=x-1}
: 如此下去得到x序列。
: 很明显，x 应该是比较接近100的一个数，x'是小于x的一个数。原则是希望每一轮总天
: 数接近。由于第二个“鸡蛋”的测试带来的是平方项，所以第一个鸡蛋测试的gap肯定
: 不是线性递减的。具体怎么算我还没什么办法。
| l****m
发帖数: 509 | 19 Amazon 的面试题为什么都是算法相关？没有别的问题吗？如果光作网页开发，用的着
这样吗？ | j**l
发帖数: 2911 | | | | j**l
发帖数: 2911 | 21 知道思想后应该可以编程穷举，从最大天数开始递减找到第一个合适的测试点，使得后
续的一系列测试点中最小的那个测试点能够到达1，然后穷举就可以停止。 | C*Y
发帖数: 736 | 22 我很久以前也被问到扔鸡蛋的题目，当时没看过那道题，挣扎半天弄了一堆方程组没弄
出结果 | a****a
发帖数: 1264 | 23 唉，赶紧回去补一下知识吧。
记得最初是给灯泡，测试灯泡的质量。
【在 K******g 的大作中提到】
: 不管怎么样，两个鸡蛋不够啊。
: 我觉得题目可能是说，让使用的鸡蛋数量最少吧。
: 谁有这题的原题？
| B*****t
发帖数: 335 | 24 是个动态规划题，和扔鸡蛋的问题的本质一样，都是求min-max。复杂度O(x^2*(k-
1)), k是第几次投诉就告失败，用上二分的话可以优化到O(xlongx*(k-1)); 扔鸡蛋那
题可以优化到O(x*k),这题估计也可以。
DP方程是：
f[x][k] = min{max{m+f[m][k], (x-m)*(m+x-1)/2}, 1<=m
写了个程序，
当x=20, k=3的时候，第一个实验16，最坏情况下必须的天数是70，
不过第一个实验17，最坏情况下必须的天数是69.
x=100, k=3, 第一个应该实验92，最坏情况下必须的最少天数是792
没有用，而且原型题也不是第一次见到就容易想到的。。。
线
探测
【在 j**l 的大作中提到】
: 说说我事后诸葛亮想到的思路吧，面试45分钟想到太难了，就算知道原型的扔鸡蛋题也没有用，而且原型题也不是第一次见到就容易想到的。。。
: 不妨简化问题便于讨论，设要求的整常数x位于区间[1, 20]之间。
: 首先，20是不用测的，如果测19的时候收到complain, 则20即所求。
: 其次，如果不幸收到一个complain, 就好比摔碎了一个鸡蛋，接下来就必须用最慢的线
: 性探测了。
: 第一个探测的天数是多少呢？我们先来看看16。
: 假如探测16收到了complain, 那么我们最坏可能必须线性探测19, 18, 17, 那么总探测
: 天数是
: 19 + 18 + 17 + 16 = 70
: 假如探测16没有complain, 下一个探测的天数是多少呢？
| j**l
发帖数: 2911 | 25 感觉你是对的，1 <= x <= 20的时候，应该从17开始试，最坏情况是69天。
19 + 18 + 17 = 54
17 + 16 + 15 + 14 = 62
17 + 14 + 13 + 12 + 11 = 67
17 + 14 + 11 + 10 + 9 + 8 = 69
17 + 14 + 11 + 8 + 7 + 6 + 5 = 68
17 + 14 + 11 + 8 + 5 + 4 + 3 + 2 + 1 = 65
DP的思路不好理解，感觉作为电面题太难。
【在 B*****t 的大作中提到】
: 是个动态规划题，和扔鸡蛋的问题的本质一样，都是求min-max。复杂度O(x^2*(k-
: 1)), k是第几次投诉就告失败，用上二分的话可以优化到O(xlongx*(k-1)); 扔鸡蛋那
: 题可以优化到O(x*k),这题估计也可以。
: DP方程是：
: f[x][k] = min{max{m+f[m][k], (x-m)*(m+x-1)/2}, 1<=m: 写了个程序，
: 当x=20, k=3的时候，第一个实验16，最坏情况下必须的天数是70，
: 不过第一个实验17，最坏情况下必须的天数是69.
: x=100, k=3, 第一个应该实验92，最坏情况下必须的最少天数是792
:
| x********r
发帖数: 1206 | | p******x
发帖数: 232 | 27 大概在700多天可以保证试出结果。思想确实与仍鸡蛋完全一样。考虑把1到100映射到1
至5050（或4950）即可。 | s***e
发帖数: 793 | 28 是典型的DP问题，扔鸡蛋也是典型的DP问题。
【在 B*****t 的大作中提到】
: 是个动态规划题，和扔鸡蛋的问题的本质一样，都是求min-max。复杂度O(x^2*(k-
: 1)), k是第几次投诉就告失败，用上二分的话可以优化到O(xlongx*(k-1)); 扔鸡蛋那
: 题可以优化到O(x*k),这题估计也可以。
: DP方程是：
: f[x][k] = min{max{m+f[m][k], (x-m)*(m+x-1)/2}, 1<=m: 写了个程序，
: 当x=20, k=3的时候，第一个实验16，最坏情况下必须的天数是70，
: 不过第一个实验17，最坏情况下必须的天数是69.
: x=100, k=3, 第一个应该实验92，最坏情况下必须的最少天数是792
:
| s***e
发帖数: 793 | 29 你的DP有点小问题，不是很精确（ (x-m)*(m+1）/2 是k=2是的特例，不能做dp方程）
，探讨一下
F(l,u,k) 是最坏可能下需要的天数。 l 是可能范围的lower bound, u 是upper
bound
K 表示最大可以接受的投诉次数。
F(1,100,2)就是本题所优化的。
当k = 1时， 只能从大往小试， 承诺99，98，97，。。。。1，所须天数是100+99+98+
97。。。+2。
F(l,u,1) = u + (u-1) + (u-2) … (l+1) = (u+l+1)*(u-l)/2
动态方程是
F(l,u,k) = min { m + 1 + Max( F( l,m,k),F(m+1,u,k-1))} l<=m<=u;
【在 B*****t 的大作中提到】
: 是个动态规划题，和扔鸡蛋的问题的本质一样，都是求min-max。复杂度O(x^2*(k-
: 1)), k是第几次投诉就告失败，用上二分的话可以优化到O(xlongx*(k-1)); 扔鸡蛋那
: 题可以优化到O(x*k),这题估计也可以。
: DP方程是：
: f[x][k] = min{max{m+f[m][k], (x-m)*(m+x-1)/2}, 1<=m: 写了个程序，
: 当x=20, k=3的时候，第一个实验16，最坏情况下必须的天数是70，
: 不过第一个实验17，最坏情况下必须的天数是69.
: x=100, k=3, 第一个应该实验92，最坏情况下必须的最少天数是792
:
| P********l
发帖数: 452 | 30 bless.
【在 j**l 的大作中提到】
: 暂时还没有收到拒信，希望可以挺过去。
| | | b********p
发帖数: 875 | | j**l
发帖数: 2911 | 32 RL是什么意思？对k = 2的特例，DP方程还是好理解的，有助于推广到k更大的情形
【在 b********p 的大作中提到】
: rl问题，dp解法
| B*****t
发帖数: 335 | 33 多谢指正，我的那个dp方程是K=2的特例，K>2时类似。
用F(l,u,k)表示状态，方程好写，不过复杂度要多乘以O(N),
注意到F(a,b,k)和F(1,b-a+1,k)的关系，可以用F(n,k)表示状态，状态转移的时候
要注意把前面略去的天数补上，具体可以递归的求出应该补上多少天，这样复杂度就可
以降一维。
方程）
upper
100+99+98+
【在 s***e 的大作中提到】
: 你的DP有点小问题，不是很精确（ (x-m)*(m+1）/2 是k=2是的特例，不能做dp方程）
: ，探讨一下
: F(l,u,k) 是最坏可能下需要的天数。 l 是可能范围的lower bound, u 是upper
: bound
: K 表示最大可以接受的投诉次数。
: F(1,100,2)就是本题所优化的。
: 当k = 1时， 只能从大往小试， 承诺99，98，97，。。。。1，所须天数是100+99+98+
: 97。。。+2。
: F(l,u,1) = u + (u-1) + (u-2) … (l+1) = (u+l+1)*(u-l)/2
: 动态方程是
| j**l
发帖数: 2911 | 34 对100层楼，2个鸡蛋的问题，共有六组解都能保证最坏情况下最多扔14次
9-->22-->34-->45-->55-->64-->72-->79-->85-->90-->94-->97-->99-->100
10-->23-->35-->46-->56-->65-->73-->80-->86-->91-->95-->98-->100
11-->24-->36-->47-->57-->66-->74-->81-->87-->92-->96-->99-->100
12-->25-->37-->48-->58-->67-->75-->82-->88-->93-->97-->100
13-->26-->38-->49-->59-->68-->76-->83-->89-->94-->98-->100
14-->27-->39-->50-->60-->69-->77-->84-->90-->95-->99-->100
第六组解是网上最常见的解答，求出1 + 2 + ... + 14刚刚超过100
第一组解是动态规划求出的解答。
第一组解，第一个鸡蛋最多共测试14层
第二组和第三组解，第一个鸡蛋最多 | l*******g
发帖数: 4894 | 35 祝福楼主，这种题目关键是得练过吃透，鸡蛋问题有一篇paper找来读读，上面写了
general的情况是怎么解决的，如果看过那片paper，或许这个问题你就好解决了。 | j**l
发帖数: 2911 | 36 那篇paper的名字？
【在 l*******g 的大作中提到】
: 祝福楼主，这种题目关键是得练过吃透，鸡蛋问题有一篇paper找来读读，上面写了
: general的情况是怎么解决的，如果看过那片paper，或许这个问题你就好解决了。
| l********s
发帖数: 30 | 37 嗯，一开始我也把它跟扔鸡蛋相类比，但不像扔鸡蛋题那样，能找出一个关于x 的简单
不等式。于是也 DP了。不过，我的结果和大家有点不同，仔细分析了大家的回复，发
现对这道题的理解略有不同。我觉得有两个问题需要澄清。
为了更清楚地说明我的思法，我定义一个 transaction 为：一个东西从 A 发到 B 地
的某个顾客，并许诺 y 天内到达。而这个 transaction 被认为是完成的，如果：y 天
过去了，没有接到用户投诉，或者接到了用户投诉。
这样，我的两个问题是：
1）能不能在一个transaction T 还没有完成之前，在某一天（可能是和发起 T 同一天
）再发起另一个 transaction W？
2）如果对 1）的回答是肯定的，那么，“最多只准收到两次投诉”，是指在找出 x 之
前，还是在所有已经发起的 transaction 都完成之后？
而我的理解是：
1）可以。否则为何要强调“顾客的数量不限制”呢？
2）都可以说得通。不同的理解有不同的解法。但个人认为，这“最多两次投诉”的限
制应该是在所有已经发起的 transaction 都完成之后，才比较符合原题的意思。
举
【在 j**l 的大作中提到】
: 那篇paper的名字？
| Z*****Z
发帖数: 723 | 38 我觉得你的优化是对的。
楼主的解法是，在求解f[i]的时候，先发一个时间为j的包裹。用了你的优化，同时再发
一个i-1的包裹，这样原来的一个worst case(sum j ... i-1)就变成了i-1，从而总的时
间变短了。
【在 l********s 的大作中提到】
: 嗯，一开始我也把它跟扔鸡蛋相类比，但不像扔鸡蛋题那样，能找出一个关于x 的简单
: 不等式。于是也 DP了。不过，我的结果和大家有点不同，仔细分析了大家的回复，发
: 现对这道题的理解略有不同。我觉得有两个问题需要澄清。
: 为了更清楚地说明我的思法，我定义一个 transaction 为：一个东西从 A 发到 B 地
: 的某个顾客，并许诺 y 天内到达。而这个 transaction 被认为是完成的，如果：y 天
: 过去了，没有接到用户投诉，或者接到了用户投诉。
: 这样，我的两个问题是：
: 1）能不能在一个transaction T 还没有完成之前，在某一天（可能是和发起 T 同一天
: ）再发起另一个 transaction W？
: 2）如果对 1）的回答是肯定的，那么，“最多只准收到两次投诉”，是指在找出 x 之
| j**l
发帖数: 2911 | 39 好像是把sum(j .. i-1)优化为sum(j+1 .. i-1), 少用了j天本身
再发
的时
【在 Z*****Z 的大作中提到】
: 我觉得你的优化是对的。
: 楼主的解法是，在求解f[i]的时候，先发一个时间为j的包裹。用了你的优化，同时再发
: 一个i-1的包裹，这样原来的一个worst case(sum j ... i-1)就变成了i-1，从而总的时
: 间变短了。
| Z*****Z
发帖数: 723 | 40 对，是这样的
【在 j**l 的大作中提到】
: 好像是把sum(j .. i-1)优化为sum(j+1 .. i-1), 少用了j天本身
:
: 再发
: 的时
| | | j**l
发帖数: 2911 | | x********r
发帖数: 1206 | 42 恭喜！ 恭喜！
【在 j**l 的大作中提到】
: 路漫漫其修远兮，吾将上下而求索。
| t*****j
发帖数: 1105 | 43 我的思路和你一样，不过编程的时候有个要注意的地方：
动态方程是
F(l,u,k) = min { m + 1 + Max( F( l,m,k),F(m+1,u,k-1))} l<=m<=u;
～～～～～～～这边1<=m
的。
可是为什么我计算机算出来的没有700天呢？
哪位高人也编一下，咱们对对结果？我的function k=2，x=20的时候返回29.
）
98+
【在 s***e 的大作中提到】
: 你的DP有点小问题，不是很精确（ (x-m)*(m+1）/2 是k=2是的特例，不能做dp方程）
: ，探讨一下
: F(l,u,k) 是最坏可能下需要的天数。 l 是可能范围的lower bound, u 是upper
: bound
: K 表示最大可以接受的投诉次数。
: F(1,100,2)就是本题所优化的。
: 当k = 1时， 只能从大往小试， 承诺99，98，97，。。。。1，所须天数是100+99+98+
: 97。。。+2。
: F(l,u,1) = u + (u-1) + (u-2) … (l+1) = (u+l+1)*(u-l)/2
: 动态方程是
|
|
