XidianOJ 1007 易碎的鸟蛋

题目描述

 你们知道吗?西电的跳楼塔上面有一个鸟巢。某SXBK的教授对这个鸟巢很感兴趣。经过仔细观察,他发现鸟巢中有若干枚蛋。于是他想利用这些蛋做一个试验。测试一下蛋的坚固程度。这些蛋应该是具有相同的坚硬度。存在一个非负整数E,如果从塔的第E层往下扔蛋,蛋不会破,但如果从第E+1层(包括高于E+1层)扔,蛋就会破。你要做一组试验,来找出E。最简单的方法是一层层试。但是你有多个蛋是,不必用笨方法,可以用更少的次数找出E。注意这里的次数都是指对你的方法的最坏情况且蛋破了就不能再用,还有E可以取0(直接放在地上蛋蛋是不会破的)。如果实验到了最高层蛋还不破,则认为E取最高层的层数。

输入

一行,蛋的个数n和楼的层数n,k<=1000。(中间一个空格)。

请一直处理到文件结束。

输出

最少实验次数。

--正文

  又是dp。。。我好讨厌dp

  方程:

  dp[i][j] = min{max{dp[i-w][j],dp[w-1][j-1]}+1, dp[i][j]};

  当我们假设蛋随便用的时候,发现就是二分,所以以题目的数据(<=1000),顶多就用10个蛋,所以n最大也就是10,对于更大的n,可以看作10个

  

#include <stdio.h>
#include <memory.h>
int min(int a,int b){
    if (a > b) return b;
    return a;
}
int max(int a,int b){
    if (a > b) return a;
    return b;
}

int main(){
    int n,k;
    while (scanf("%d %d",&n,&k) != EOF){
        int dp[1005][20];
        memset(dp,0x3f,sizeof(dp));
        if (n > 10) n = 10;
        int i,j,w;
        for (i=0;i<=n;i++){
            dp[0][i] = 0;
            dp[1][i] = 1;
        }
        for (i=0;i<=k;i++){
            dp[i][1] = i;
        }
        for (i=2;i<=k;i++){
            for (j=2;j<=n;j++){
                for (w=1;w<=i;w++){
                    dp[i][j] = min(dp[i][j],max(dp[w-1][j-1],dp[i-w][j]) + 1);
                }
            }
        }    
        printf("%d
",dp[k][n]);
    }
    
    return 0;
} 
原文地址:https://www.cnblogs.com/ToTOrz/p/6062047.html