我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理

URAL--1223--DP(鹰蛋实验)

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


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理