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个鸡蛋至少要试多少次

 1 # include <stdio.h>
 2 # include <limits.h>
 3 #define INF 2000000010
 4 int max(int a, int b) { return (a > b)? a: b; }
 5 int eggFloor[100][1000];
 6 int eggDrop(int n, int k)
 7 {
 8     /* eggFloor[i][j] 表示对于 i个鸡蛋 j 层楼，需要的最少测试次数 */
 9     int res;
10     int i, j, x;
11     // 初始化
12     for (i = 1; i <= n; i++)
13     {
14         eggFloor[i][1] = 1;
15         eggFloor[i][0] = 0;
16     }
17  
18     //只有一个鸡蛋，没得优化，需要j次
19     for (j = 1; j <= k; j++)
20         eggFloor[1][j] = j;
21  
22     // 最优子结构的递推
23     for (i = 2; i <= n; i++)
24     {
25         for (j = 2; j <= k; j++)
26         {
27             eggFloor[i][j] = INT_MAX;
28             for (x = 1; x <= j; x++)
29             {
30                 res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
31                 if (res < eggFloor[i][j])
32                     eggFloor[i][j] = res;
33             }
34         }
35     }
36 }
37 int a[2][40][40];
38 int init()
39 {
40     for(int i=1;i<=32;i++) { a[1][i][1]=a[0][i][1]=1;a[1][i][0]=a[0][i][0]=0; }
41     for(int j=1;j<=32;j++) a[0][1][j]=a[1][1][j]=j;
42     for(int i=2;i<=32;i++)//egg
43     {
44         for(int j=2;j<=32;j++)//floor
45         {
46             a[0][i][j]=a[1][i][j-1]+1;
47             a[1][i][j]=a[0][i][j]+a[1][i-1][j-1];
48             if(a[0][i][j]<0) a[0][i][j]=INF;
49             if(a[1][i][j]<0) a[1][i][j]=INF;
50         }
51     }
52     for(int i=1;i<=32;i++,printf("
"))
53         for(int j=1;j<=32;j++)
54             printf("%2d,%2d ",a[0][i][j],a[1][i][j]);
55 }
56 int b[40][40];
57 int init1()
58 {
59     for(int i=1;i<=33;i++) { b[i][1]=1;b[i][0]=0; }
60     for(int j=1;j<=33;j++) b[1][j]=j;
61     for(int i=2;i<=33;i++)
62     {
63         for(int j=2;j<=33;j++)
64         {
65             b[i][j]=1+b[i][j-1]+b[i-1][j-1];
66             if(b[i][j]<0) b[i][j]=INF;
67         }
68     }
69 /*    for(int i=1;i<=33;i++,printf("
"))
70         for(int j=1;j<=33;j++)
71             printf("%d ",b[i][j]);*/
72 }
73 /* 测试*/
74 int main()
75 {
76 //    freopen("out","w",stdout);
77 //    init();
78     init1();
79     int n,k,i,T;
80     scanf("%d",&T);
81     while(T--)
82     {
83         scanf("%d%d",&n,&k);
84         for(i=1;i<=32;i++) if(n<=b[k][i]) break;
85         i<=32?printf("%d
",i):puts("Impossible");
86     }
87     return 0;
88     eggDrop(n,k);
89     for(int i=1;i<=n;i++)//egg
90     {
91         for(int j=1;j<=k;j++) printf("%2d ",eggFloor[i][j]);
92         printf("
");
93     }
94     return 0;
95 }

View Code