玻璃780
幼苗
共回答了17个问题采纳率:94.1% 举报
这题应有个上限,就是鸡蛋扔多少米一定会坏,设为h米
设T(i,j)为用i个鸡蛋,上限为j米,最坏情况下最少次数.
i从1到n,j从1到h
T(1,j)=j-1 即只有一个鸡蛋,需要从一米开始一直到j-1米,要j-1次
T(i,1)=0 即当1米一定摔坏,则碎点是0,不需要扔即可知道
当i>1且j>1时
其中
k表示扔一个鸡蛋在k米
T(i,j-k)+1 是指鸡蛋扔在k层没摔坏,则等于i个鸡蛋,最坏j-k米需要次数+1
T(i-1,k)+1 是指鸡蛋扔在k层摔坏,则等于i个鸡蛋,最坏k米需要次数+1
max 是指两种情况下最坏需要的次数
min 在1到j-1米中选择最坏情况下最小次数的米数
1年前
4