Posted on 2008-08-01 23:53
Hero 阅读(640)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗--ACM
第一想法二分,不过是错的。
假设有i层j个蛋,在第k层做实验丢下一个蛋,这个蛋有两个状态1)碎了2)没碎。
1)当蛋碎了那我们就只需要找前k-1层,因为蛋碎了所以还有j-1个蛋
2)当蛋没有碎那我们就只需要找后面的i-k层,因为蛋没有碎所以还有j个蛋
因为是最坏情况,所以应该是两种情况中最大的一个
我们就可以得到动态转移方程了:
设f[i,j]表示有i层j个蛋做实验的最坏情况的最小植
所以f[i,j] = min{max{f[k-1,j-1],f[i-k,j]}+1} (1<=k<=i)
但这个方程的时间复杂度是O(N3),对10003是肯定要超时的。前面说了二分得到的答案不是最优,不过在二分的过程中我们发现1000层最多也就10个蛋,所以但蛋的个数大于10的时候项当于只有10个蛋。所以蛋只当它有10个,所以现在的时间复杂度为O(1000*1000*10)就不会超时了。