ITKeyword,专注技术干货聚合推荐

注册 | 登录

POJ 3783 Balls(扔鸡蛋问题——DP动态规划)

qingshui23 分享于 2016-08-03

推荐:大楼扔鸡蛋问题 dp poj 3783

题意分析: 经典题,小白书上的一道例题,4+2出了这道原题,我愣是以为是数学题,最后也没做出来。题意是这样的,给你N个鸡蛋(硬度一样),让你测鸡蛋的硬度,

2019阿里云双11返场狂欢继续,
地址https://www.aliyun.com/1111/2019/home

传送门 Balls Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 892 Accepted: 588 Description The classic Two Glass Balls brain-teaser is often posed as: “Given two identical glass spheres, you would like to determine the lowest floor in a 100-story building from which they will break when dropped. Assume the spheres are undamaged when dropped below this point. What is the strategy that will minimize the worst-case scenario for number of drops?” Suppose that we had only one ball. We’d have to drop from each floor from 1 to 100 in sequence, requiring 100 drops in the worst case. Now consider the case where we have two balls. Suppose we drop the first ball from floor n. If it breaks we’re in the case where we have one ball remaining and we need to drop from floors 1 to n-1 in sequence, yielding n drops in the worst case (the first ball is dropped once, the second at most n-1 times). However, if it does not break when dropped from floor n, we have reduced the problem to dropping from floors n+1 to 100. In either case we must keep in mind that we’ve already used one drop. So the minimum number of drops, in the worst case, is the minimum over all n. You will write a program to determine the minimum number of drops required, in the worst case, given B balls and an M-story building. Input The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set consists of a single line containing three(3) decimal integer values: the problem number, followed by a space, followed by the number of balls B, (1 ≤ B ≤ 50), followed by a space and the number of floors in the building M, (1 ≤ M ≤ 1000). Output For each data set, generate one line of output with the following values: The data set number as a decimal integer, a space, and the minimum number of drops

推荐:POJ 1163 The Triangle & POJ 3176 Cow Bowling(DP动态规划)

买一送一的动态规划题目,让我开心地AC两次!唯一改变的就是数组的大小。 Description The cows don't use actual bowling balls when they go bowling. They ea

needed for the corresponding values of B and M. Sample Input 4

1 2 10

2 2 100

3 2 300

4 25 900 Sample Output 1 4 2 14 3 24 4 10 题目大意: 有一些鸡蛋,我们现在想知道这些鸡蛋的硬度。然后现在有一座很高很高的大楼里,我们现在要在这座大楼上测试鸡蛋的硬度。每个鸡蛋的硬度相同,鸡蛋的硬度定义为:如果鸡蛋从第 m 层上掉下来没有破裂,而从第 m+1 层上掉下来就破裂了,那么这个鸡蛋的硬度就是 m 。某个鸡蛋如果在实验中破裂了就永远的损失了。我们现在有 n 个鸡蛋。那么在最坏情况下我们最少需要做多少次实验呢? 输入数据:是 T 组数据,然后第一个数 是标号 op ,然后输入两个整数 M ,和 N ,分别表示有 M 个鸡蛋和 N 层楼。 输出数据:标号 op , 和最坏情况下我们最少需要做多少次实验 ans 解题思路: 这是一个比较经典的 DP 问题,又叫做 “扔鸡蛋问题”,假设 dp[n,m] 表示 n 层楼、 m 个鸡蛋时找到摔鸡蛋不碎的最少判断次数。则一个鸡蛋从第 i 层扔下,如果碎了,还剩 m−1 个鸡蛋,为确定下面楼层中的安全位置,还需要 dp[i−1,m−1] 次(子问题);不碎的话,上面还有 n−i 层,还需要 dp[n−i,m] 次(子问题,实体 n 层楼的上 n−i 层需要的最少判断次数和实体 n−i 层楼需要的最少判断次数其实是一样的)。 /** 2016 - 08 - 03 上午 Author: ITAK Motto: 今日的我要超越昨日的我,明日的我要胜过今日的我, 以创作出更好的代码为目标,不断地超越自己。 **/#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <vector>#include <queue>#include <algorithm>#include <set>using namespace std;typedef long long LL;typedef unsigned long long ULL;const int INF = 1e9+5;const int MAXN = 1e3+5;const int MOD = 1e9+7;const double eps = 1e-7;int dp[MAXN][60];///dp[i][j]:表示在 i 层楼 还有 j 个鸡蛋的最小判断次数void Solve(int M, int N){

memset(dp, 0, sizeof(dp));///初始化

for(int i=1; i<=N; i++)///就一个鸡蛋,肯定是从第一层往上尝试的

dp[i][1] = i;

for(int i=1; i<=M; i++)///就一层,肯定是 1

dp[1][i] = 1;

for(int i=1; i<=N; i++)

{

for(int j=2; j<=M; j++)

{

dp[i][j] = INF;///初始化为比较大的值

for(int k=1; k<=i; k++)

dp[i][j] = min(dp[i][j],max(dp[k-1][j-1],dp[i-k][j])+1);

}

}}int main(){

int op, N, M, T;

scanf("%d",&T);

while(T--)

{

scanf("%d%d%d",&op,&M,&N);///N层 M个

Solve(M, N);

printf("%d %d\n",op, dp[N][M]);

}

return 0;}

推荐:POJ 1837 Balance(DP动态规划)

//DP,动态规划求组合数,dp[i][j]表示前i个重锤获得重量j有几种方式 //转移方程dp[i][j+k] += dp[i-1][j];k为新添加第I个重锤的质量 //对重锤对应钩子将其分组后

传送门 Balls Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 892 Accepted: 588 Description The classic Two Glass Balls brain-teaser is often posed as: “Given two identi

相关阅读排行


用户评论

游客

相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。