Posted on 2008-08-01 23:53
Hero 阅读(620)
评论(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)就不会超时了。