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