POJ 3783 - Balls

http://poj.org/problem?id=3783

概要

あるガラス玉を M 階建の建物のどの階から落としたときに最初に割れるのかを知りたい．

もしガラス玉が1つしかない場合は，1階から順に試していくしかないので，最悪のケースでは M-1 回の試行が必要になる．

B 個の全く同質のガラス玉があった場合を考えて，最悪のケースでの試行回数を最小化したとき，その最小値を答える．

制約

• 1 <= テストケース数 <= 1000
• 1 <= B <= 50
• 1 <= M <= 1000

解法

dp[i][j] = i 個のガラス玉で j 階建の建物で調べたときの答え

として，DP で最初にすべての答えを求めておく．

dp[i][j] は，ある k 階からガラス玉を落とした場合，

• 割れたら dp[i-1][k-1] の状況
• 割れなかったら dp[i][j-k] の状況

なので，

dp[i][j] = min { max(dp[i][j], dp[i][j-k]) } for k = 1 ... j

と更新できる．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   static int dp[51][1001];
 8   for (int j = 1; j <= 1000; j++) {
 9     dp[1][j] = j;
10   }
11   for (int i = 2; i <= 50; i++) {
12     for (int j = 1; j <= 1000; j++) {
13       dp[i][j] = j;
14       for (int k = 1; k <= j; k++) {
15         dp[i][j] = min(dp[i][j], max(dp[i-1][k-1], dp[i][j-k]) + 1);
16       }
17     }
18   }
19 
20   int P;
21   scanf("%d", &P);
22   while (P-- > 0) {
23     int p, B, M;
24     scanf("%d %d %d", &p, &B, &M);
25     printf("%d %d\n", p, dp[B][M]);
26   }
27   return 0;
28 }