URAL 1223 Chernobyl’ Eagle on a Roof

题意

经典的蛋碎问题
现在有n个蛋，有相同的坚硬程度。
每次测试从一个任意的高度H往下扔，
如果蛋碎了，则其坚硬程度

题解

直接考虑非常困难，有下面的设法：
$f(i，j)$ 代表用i个蛋砸j次可以确定的最大楼层数
边界初值显见$f(1,i)=i$
$f(0,i)=0$
$f(i,0)=0$
$f(i,1)=1$
对于(i,j)，如果在$H>f[i-1][j-1]+1$的位置投掷，一旦破碎，则无法判定其准确位置，
故最多只能在$H = f[i-1][j-1]+1$位置投掷。
1. 如果投掷破碎，则划归为$(i-1,j-1)$的问题（因为$(i-1,j-1)$可以判定$\leq f[i-1][j-1]$的高度）
2. 如果投掷不破碎，则划归为$(i-1,j)$的问题（如果不破碎，那么高度为$H$与高度为$0$就没差了）
即问题重新变为在已有$f[i-1][j-1]+1$的高度下，判定蛋碎的高度。还能再算$f[i-1][j]$那么多高度
综上，$f[i][j] = f[i-1][j-1] + 1 + f[i-1][j]$

code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include const int maxn = 1010;int f[maxn][maxn];
int n, m;bool solve() {if (!(scanf("%d%d", &n, &m) == 2 && n)) return 0;for (int j = 1; j <= m; ++ j)if (f[n][j] >= m) {printf("%d\n", j);return 1;}return 1;
}int main() {memset(f, 0, sizeof f);for (int i = 1; i <= 1000; ++ i)for (int j = 1; j <= 1000; ++ j)f[i][j] = f[i][j-1] + f[i-1][j-1] + 1;//  freopen(".in", "r", stdin);while (solve());//  for(;;);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！