Description
Input
Output
Sample Input
| input | output |
|---|---|
1 10 2 5 0 0 |
10 3 |
大意：摔蛋，每一个蛋的坚固系数相同，问最少的摔蛋次数，不断二分，直到最后一个不能摔碎，考虑到二分，而且塔的高度不超过1000，所以最多摔碎10个蛋1024就行了
定义 dp[i][j] 表示用了i个蛋，需要测j楼层的摔蛋次数
动态转移方程 dp[i][j] = min(dp[i-1][j-1],dp[i][n-j]) 摔碎和没摔碎
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[15][1110];
const int inf = 0x3f3f3f3f;
int dfs(int x,int y)
{
if(dp[x][y])
return dp[x][y];
if(x == 1){
dp[x][y] = y;
return y;
}
if(y <= 2){
dp[x][y] = y;
return y;
}
int min1 = inf;
for(int i = 2; i < y; i++){
int max1 = max(dfs(x,y-i)+1,dfs(x-1,i-1)+1);
min1 = min(min1,max1);
}
dp[x][y] = min1;
return min1;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)&&(n&&m)){
if(n > 10)
n = 10;
printf("%d\n",dfs(n,m));
}
return 0;
}
URAL1223——DFS—— Chernobyl’ Eagle on a Roof
原文：http://www.cnblogs.com/zero-begin/p/4498318.html