有k个“硬度”相同的水气球，从一定高度摔下来才会破，然后有一栋n层高大楼供你测试气球的硬度。如果气球从第f层落下不会破，而从f+1层落下就会破，那它的硬度就是f，如果从最高层n也不会破，认为它的硬度是n。
（1≤k≤100，1≤n<2^63）
问最少需要做几次实验，才能确定气球的硬度。如果63次不够，输出"More than 63 trials needed."
设dp(t,i)为t个气球、测i次能够确定硬度的最大范围，即硬度1~dp(t,i)。如果dp(t,i)>=n，则t个气球测i次就一定能够测出来，否则t个气球测i次无法确定气球硬度。
然后，考虑dp(t,i)所对应的测试方案中第一次选择的楼层，假定为a，把气球从a层抛下去，就要做好摔破的准备，如果它破了，说明硬度<a，那么你还剩下t-1个气球和i-1次实验，必须能够确定出1~a-1的硬度范围，即dp(t-1,i-1)须>=a-1，换句话说，我们选择的a不能太大，须有a<=dp(t-1,i-1)+1。如果在第a层没破，说明硬度>=a，还剩下t个气球和i-1次实验，为了尽可能地扩大可确定的范围，我们应当把第a层当作第1层，使用dp(t,i-1)的方法测量以上楼层，这是最优的，这样所能确定的最大范围是1~a+dp(t,i-1)，即dp(t,i)=max{a+dp(t,i-1)}=dp(t-1,i-1)+1+dp(t,i-1).
网友评论