[LeetCode 887. 鸡蛋掉落] DP+二分

1. 题目链接

[LeetCode 887. 鸡蛋掉落]

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$.
感觉理论上三分应该也是可以的,但是不知道为什么三分就是不太对…~

4. 参考代码##

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include 
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const long double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

int dp[105][10005];

class Solution {
public:
int superEggDrop(int K, int N) {
memset(dp, 0x3f, sizeof(dp));
for(int i = 0; i <= k;="" ++i)="" dp[i][1] = 0;
for(int j = 1; j <= n="" +="" 1; ++j) dp[1][j] = j - 1;
for(int i = 2; i <= k;="" ++i)="" {<="" span="">
for(int j = 2; j <= n="" +="" 1; ++j) {

//for(int m = j/2; m <= j;="" ++m)="" <="" span="">
//dp[i][j] = min(dp[i][j], max(dp[i - 1][j - m], dp[i][m]) + 1);
/*
int lb = 0, ub = j, lmd, rmd;
while(lb <= ub)="" {<="" span="">
lmd = (lb + ub) >> 1, rmd = (lmd + ub) >> 1;
int lval = max(dp[i - 1][j - lmd], dp[i][lmd]);
int rval = max(dp[i - 1][j - rmd], dp[i][rmd]);
dp[i][j] = min(lval, rval) + 1;
if(lval == rval) lb = lmd + 1, ub = rmd - 1;
else if(lval < rval) ub = rmd;
else lb = lmd;
}
if(0 <= lb="" &&="" <="j)" dp[i][j]="min(dp[i][j]," max(dp[i="" -="" 1][j="" lb],="" dp[i][lb])="" +="" 1);<="" span="">
if(0 <= ub="" &&="" <="j)" dp[i][j]="min(dp[i][j]," max(dp[i="" -="" 1][j="" ub],="" dp[i][ub])="" +="" 1);<="" span="">
*/
int lb = 0, ub = j;
while(lb <= ub)="" {<="" span="">
int md = (lb + ub) >> 1;
dp[i][j] = min(dp[i][j], max(dp[i - 1][j - md], dp[i][md]) + 1);
if(dp[i - 1][j - md] == dp[i][md]) lb = md + 1, ub = md - 1;
else if(dp[i - 1][j - md] > dp[i][md]) lb = md + 1;
else ub = md - 1;
}
}
}
return dp[K][N + 1];
}
};

#ifdef __LOCAL_WONZY__
int main() {
freopen("input.txt", "r", stdin);
Solution solu;
cout << solu.superEggDrop(1, 2) << endl;
cout << solu.superEggDrop(2, 6) << endl;
cout << solu.superEggDrop(3, 14) << endl;
cout << solu.superEggDrop(3, 200) << endl;
return 0;
}
#endif
坚持原创技术分享,您的支持将鼓励我继续创作!