题意:给定B (B <= 50) 个一样的球,从 M (M <= 1000) 层楼上一个一个往下扔,存在某个楼层K,使得低于它的楼层往下扔球,球不会碎,在第K层扔下去会碎。求最坏情况下,需要扔几次才能确定这个K。
方法就是动态规划了。 虽然刚开始一直以为是个贪心或者构造
dp[i][j] 表示有i层楼, 剩余j个球时, 最坏情况要确定K 所需的次数
那么在这些楼层里
我们可以选择在k层(1<= k <= i)扔
有两种情况,破跟不破
(1)不破, 则排除掉了k层,剩余i-k层 则转化为 dp[i - k][j]
(2)破了 则剩余i - 1层, 球剩k - 1个 转化为 dp[i - 1][ k - 1]
然后由于是最坏情况,所以对于特定的 k
dp[i][j] = min(dp[i][j], max(dp[i - k][j], dp[i - 1][ k - 1]) + 1 )
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <map>
#include <ctime>
#define MAXN 111111
#define MAXM 1122222
#define INF 1000000001
#define eps 1e-8
using namespac