【題意】：給出k個郵筒，郵筒理論承受爆炸能力為m，實際上是[1,m]的某一個值。問，最壞情況下， 至少要用多少炸藥才能測試出郵筒的承受爆炸能力。
               有幾點要注意：
               1.如果郵筒可以承受x單位炸藥，必定可以承受1到x-1單位的炸藥。
               2.除非郵筒某次測試中被炸毀，否則仍然當它是完好無缺的，可以繼續用于下一次測試。
               
【題解】：dp。
               對于只有一個郵筒，我們只能由1,2,3,……,m-1,m測試，所以最壞情況就是(1+m) * m / 2。
               設狀態dp[i][l][r] 表示當前還有 i 個郵筒，且承受能力在[l,r]內測試出承受爆炸能力所用的最少炸藥。
               
               顯然：
                     i == 1時，dp[1][l][r] = (l + r) * (r - l + 1) / 2.
                     i >= 2時，我們就不需要從頭開始枚舉了，我們應該選擇一個最優的分界點去測試。
                           所以有 dp[i][l][r] = min(dp[i][l][r], s + max(dp[i][s+1][r], dp[i-1][l][s-1])), l <= s <= r;
                     這里說明一下，因為測試完點s之后，題目要求是最壞情況，所以只能選較大那個。
                     而外層的min是指，在這么多分界點之中，我們選取最優的分界點，這樣才能保證用最少炸藥。

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 const int inf = 1 << 30;
19 int k, m;
20 int dp[11][101][101];
21 
22 void init_dp() {
23     for(int r = 1; r <= 100; r++)
24         for(int l = 1; l <= r; l++)
25             dp[1][l][r] = (l + r) * (r - l + 1) / 2;
26 
27     for(int i = 2; i <= 10; i++) {
28         for(int r = 1; r <= 100; r++) {
29             for(int l = r; l; l--) {
30                 dp[i][l][r] = inf;
31                 for(int s = l; s <= r; s++) 
32                     dp[i][l][r] = min(dp[i][l][r], s + max(dp[i][s+1][r], dp[i-1][l][s-1]));
33             }
34         }
35     }
36 }
37 
38 int main() {
39     int T;
40     scanf("%d", &T);
41     init_dp();
42     while(T--) {
43         scanf("%d%d", &k, &m);
44         printf("%d\n", dp[k][1][m]);
45     }
46     return 0;
47 }
48