Posted on 2008-08-01 23:53
Hero 閱讀(674)
評論(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)就不會超時了。