zstu 4214 高楼扔鸡蛋(google 面试题)dp

input

T　　1<=T<=10000

n m　　1<=n<=2000000007 1<=m<=32

output

m个鸡蛋从1到n哪一楼x扔下去刚好没碎，而再x+1楼扔下去就碎了，求最少扔的次数无论x为1到n的哪个数都能确定x

如果x>32,输出Impossible，否则输出x

做法：dp，d(x,y)=d(x,y-1)+d(x-1,y-1),x:egg,y:floor求出下限，即x个鸡蛋至少要试多少次

 # include <stdio.h>

 # include <limits.h>

 #define INF 2000000010

 int max(int a, int b) { return (a > b)? a: b; }

 int eggFloor[][];

 int eggDrop(int n, int k)

 {

     /* eggFloor[i][j] 表示对于 i个鸡蛋 j 层楼，需要的最少测试次数 */

     int res;

     int i, j, x;

     // 初始化

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

     {

         eggFloor[i][] = ;

         eggFloor[i][] = ;

     }

     //只有一个鸡蛋，没得优化，需要j次

     for (j = ; j <= k; j++)

         eggFloor[][j] = j;

     // 最优子结构的递推

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

     {

         for (j = ; j <= k; j++)

         {

             eggFloor[i][j] = INT_MAX;

             for (x = ; x <= j; x++)

             {

                 res =  + max(eggFloor[i-][x-], eggFloor[i][j-x]);

                 if (res < eggFloor[i][j])

                     eggFloor[i][j] = res;

             }

         }

     }

 }

 int a[][][];

 int init()

 {

     for(int i=;i<=;i++) { a[][i][]=a[][i][]=;a[][i][]=a[][i][]=; }

     for(int j=;j<=;j++) a[][][j]=a[][][j]=j;

     for(int i=;i<=;i++)//egg

     {

         for(int j=;j<=;j++)//floor

         {

             a[][i][j]=a[][i][j-]+;

             a[][i][j]=a[][i][j]+a[][i-][j-];

             if(a[][i][j]<) a[][i][j]=INF;

             if(a[][i][j]<) a[][i][j]=INF;

         }

     }

     for(int i=;i<=;i++,printf("\n"))

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

             printf("%2d,%2d ",a[][i][j],a[][i][j]);

 }

 int b[][];

 int init1()

 {

     for(int i=;i<=;i++) { b[i][]=;b[i][]=; }

     for(int j=;j<=;j++) b[][j]=j;

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

     {

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

         {

             b[i][j]=+b[i][j-]+b[i-][j-];

             if(b[i][j]<) b[i][j]=INF;

         }

     }

 /*    for(int i=1;i<=33;i++,printf("\n"))

         for(int j=1;j<=33;j++)

             printf("%d ",b[i][j]);*/

 }

 /* 测试*/

 int main()

 {

 //    freopen("out","w",stdout);

 //    init();

     init1();

     int n,k,i,T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&k);

         for(i=;i<=;i++) if(n<=b[k][i]) break;

         i<=?printf("%d\n",i):puts("Impossible");

     }

     return ;

     eggDrop(n,k);

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

     {

         for(int j=;j<=k;j++) printf("%2d ",eggFloor[i][j]);

         printf("\n");

     }

     return ;

 }