POJ 3783 Balls --扔鸡蛋问题经典DP

题目链接

这个问题是谷歌面试题的加强版，面试题问的是100层楼2个鸡蛋最坏扔多少次：传送门。

下面我们来研究下这个题，B个鸡蛋M层楼扔多少次。

题意：给定B (B <= 50) 个一样的球，从 M (M <= 1000) 层楼上一个一个往下扔，存在某个楼层K，使得低于它的楼层往下扔球，球不会碎，在第K层扔下去会碎。求最坏情况下，需要扔几次才能确定这个K。

dp[i][j] 表示有i层楼，剩余j个球时，最坏情况要确定K 所需的次数

那么在这些楼层里

我们可以选择在k层(1<= k <= i)扔

有两种情况，破跟不破

(1)不破，则排除掉了k层，剩余i-k层则转化为 dp[i - k][j]

(2)破了则剩余k- 1层，球剩j - 1个转化为 dp[k - 1][ j - 1]

然后由于是最坏情况，所以对于特定的 k

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

#include <cstdio>

#include <iostream>

using namespace std;

const int inf=0x3f3f3f3f;

int dp[][];

int main()

{

    //注意如果100层楼1个鸡蛋 需要测100次 即存在100次以后还不碎的情况

    int t,cas=;

    scanf("%d",&t);

    while(t--){

        int n,m;

        scanf("%*d%d%d",&m,&n);//n层楼 m个鸡蛋

        for(int i=;i<=n;i++) dp[i][]=i; //1个鸡蛋 肯定得从第一层全测一遍

        for(int j=;j<=m;j++) dp[][j]=; //1层楼肯定测一次

        for(int i=;i<=n;i++)

        for(int j=;j<=m;j++){//从第二层楼开始测

            dp[i][j]=inf;

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

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

        }

        printf("%d %d\n",cas++,dp[n][m]);

    }

    return ;

}

巴特西

POJ 3783 Balls --扔鸡蛋问题经典DP

最新文章

热门文章

巴特西

POJ 3783 Balls --扔鸡蛋问题 经典DP

最新文章

热门文章

POJ 3783 Balls --扔鸡蛋问题经典DP