1. 题目链接
2. 题目描述##
3. 解题思路##
首先,令$dp[i][j+1]$表示有$i$个鸡蛋,建筑物为 $j$层时的答案. 那么, 我们容易想到下面的DP的状态转移方程:
$$dp[i][j]=\mathrm{min}{\mathrm{max}(dp[i-1][j-k],dp[i][k])+1}$$
其中, $k\in [0, j]$.
此时, DP的复杂度是$O(KN^2)$. 打表或者直接分析转移方程,可以发现, $dp[i][j]>=dp[i][j-1], dp[i][j]<=dp[i-1][j]$.
那么, 对于给定$i,j$, $dp[i-1][j-k]$随$k$单调递减,$dp[i-1][k]$随$k$单调递增.那么可以二分找到使得 $\mathrm{max}(dp[i-1][j-k],dp[i][k])+1}$最小的$k$.
感觉理论上三分应该也是可以的,但是不知道为什么三分就是不太对…~=dp[i-1][j]$.
4. 参考代码##
1 |
|