首页 > 代码库 > POJ3783Balls[DP 最坏情况最优解]
POJ3783Balls[DP 最坏情况最优解]
Balls
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 907 | Accepted: 598 |
Description
The classic Two Glass Balls brain-teaser is often posed as:
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.
"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 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 42 143 244 10
Source
Greater New York Regional 2009
------------------------------------------------
经典问题
----------------------------
f[i][j]表示i层楼j个蛋的最坏情况最优解
两种可能,碎或不碎f[i][j]=min(f[i][j],max(f[i-1][k-1],f[i][j-k])+1)
初始化INF,f[i][0]=0,f[1][j]=j 不是j-1
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int N=1005,B=55,INF=1e9;int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int p,b,m,ans=INF,no;int f[B][N];void dp(){ for(int i=0;i<=b;i++) for(int j=1;j<=m;j++) f[i][j]=INF,f[1][j]=j; for(int i=1;i<=b;i++) for(int j=1;j<=m;j++) for(int k=1;k<=j;k++) f[i][j]=min(f[i][j],max(f[i-1][k-1],f[i][j-k])+1);}int main(int argc, const char * argv[]) { p=read(); for(int i=1;i<=p;i++){ no=read();b=read();m=read(); dp(); ans=f[b][m]; printf("%d %d\n",no,ans); } return 0;}
POJ3783Balls[DP 最坏情况最优解]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。