昨天早上看了題經(jīng)典老題，拋玻璃球，也有的版本是拋雞蛋，可惜昨天早上愣是沒(méi)做出來(lái)，下午忙別的事去了，到了晚上看了ChinaUnix上的一篇
討論帖才知道如何解，事實(shí)上我一開(kāi)始對(duì)題目的理解就錯(cuò)了，于是根本沒(méi)有想到用DP。今天總算有時(shí)間整理一下思路，并把代碼實(shí)現(xiàn)出來(lái)了。
題目是這樣的：一個(gè)100層的大廈，你手中有兩個(gè)相同的玻璃球。從這個(gè)大廈的某一層扔下圍棋
子就會(huì)碎，用你手中的這兩個(gè)玻璃圍棋子，找出一個(gè)最優(yōu)的策略，來(lái)得知那個(gè)臨界層面。
這里的最優(yōu)策略指的是在這種策略下無(wú)論哪個(gè)臨界層面在第幾層，測(cè)試的次數(shù)最少。我一開(kāi)始就是把題意理解錯(cuò)了，給了一個(gè)非最優(yōu)解，后來(lái)看了CU那的討論后才明白了是用動(dòng)態(tài)規(guī)劃來(lái)做，并可以把題目擴(kuò)展為n層大廈用k個(gè)玻璃球來(lái)測(cè)試。
設(shè)F(n,k)為用k個(gè)玻璃球來(lái)測(cè)試n層大廈的臨界層的最少次數(shù)，狀態(tài)轉(zhuǎn)移方程如下：
F(n,k)=min{max{F(r,k-1), F(n-r,k)}+1, 1<=r<=n}
邊界條件:F(n,1)=n-1, F(1,k)=F(0,k)=0
狀態(tài)轉(zhuǎn)移方程可以這樣來(lái)考慮，假設(shè)在n層樓中的第r層拋一次(對(duì)應(yīng)方程中的"+1")，會(huì)有兩種情況發(fā)生：
(1)玻璃球碎，說(shuō)明在第1到第r層樓中必有一層為臨界層，問(wèn)題轉(zhuǎn)化為一個(gè)子問(wèn)題：求F(r,k-1)
(2)玻璃球不碎，說(shuō)明臨界層在第r+1層到第n層這n-r層樓中，問(wèn)題轉(zhuǎn)化為子問(wèn)題:求F(n-r,k)
因?yàn)榭紤]的是最壞情況下拋球策略的所需測(cè)試次數(shù)的最小值，所以取這兩種情況中的較大值，并遍歷每一個(gè)可能的r，取其最小值即得到F(n,k)。
實(shí)現(xiàn)代碼如下：
1 #include <iostream>
2 #include <fstream>
3 #include <sstream>
4 #include <string>
5 #include <cmath>
6 #include <iomanip>
7 #include <vector>
8 #include <deque>
9 #include <list>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <algorithm>
14 #include <limits>
15 #include <utility>
16 #include <ctime>
17 #include <bitset>
18 using namespace std;
19
20 #define MAX_FLOOR 512
21 #define MAX_BALL 100
22
23 int dp(int n, int k)
24 {
25 if(k<1 || n<1) return -1; //錯(cuò)誤輸入
26
27 if(k==1) return n-1; //去掉一些trivial case
28 if(n==1) return 0;
29
30 int M[MAX_BALL][MAX_FLOOR];
31 int i,j,r;
32 int temp, min;
33
34 for(i=0;i<=k;i++) M[i][0]=M[i][1]=0; //F(1,k)=F(0,k)=0
35 for(j=2;j<=n;j++) M[1][j]=j-1; //F(n,1)=n-1
36
37 /*
38 狀態(tài)轉(zhuǎn)移方程：
39 F(n,k)=min{max{F(r,k-1)+1, F(n-r,k)+1}, 1<=r<=n}
40 */
41 for(i=2;i<=k;i++)
42 for(j=2;j<=n;j++)
43 {
44 min = numeric_limits<int>::max();
45 for(r=1;r<=j;r++)
46 {
47 temp = max(M[i-1][r], M[i][j-r])+1;
48 if(temp<min)
49 min = temp;
50 }
51 M[i][j] = min;
52 }
53
54 return M[k][n];//F(n,k)
55 }
56
57 int main()
58 {
59 int n,k;
60
61 cin>>n>>k;
62 cout<<dp(n, k)<<endl;
63
64 return 0;
65 }
input: 100 2 output: 14
input: 300 3 output: 13