【题意】:给出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