题目大意：

给出$k$个油桶，给出油桶被炸掉的最小限度的上限，问在最坏情况下需要炸药最少的决策条件下需要的炸药。

题目分析：

首先定义状态$dp[i][j][k]$是还剩$i$个油桶且当前需要进行判断的区间是$j-k$的时候的最优值，这样的话$dp[i][j][k]$的情况一定是最坏的我们不能决定，但我们能够进行决策，也就是我们能够确定在当前状态下选择检验的量，对于每个选择的检验量，会有两种情况，第一种情况是油桶的最小承受限度小于检验量，那么这个油桶就炸掉了，那么就是转移到$dp[i-1][j][t-1]+t$，另一种情况最小承受限度大于检验量，那么这个油桶还在，同样我们的检测区间也变小了，也就是转移到$dp[i][t+1][k]$,因为是在最坏情况下，所以要在两种情况中取较大的，然后因为要通过决策得到最优解，也就是最小值，所以枚举$t$求解最小值

标程

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 107
#define INF (1 << 29)

using namespace std;

int n, k, m;
int dp[20][MAX][MAX];

void init() {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i < MAX; i++)
        for (int j = i; j < MAX; j++)
            dp[1][i][j] = (j - i + 1) * (i + j) / 2;

    for (int i = 2; i <= 10; i++)
        for (int j = 1; j <= 100; j++)
            for (int k = j; k > 0; k--) { // 注意：这里的变量k与全局变量k重名，但C++98允许局部变量覆盖全局变量
                dp[i][k][j] = INF;
                for (int t = k; t <= j; t++)
                    dp[i][k][j] = min(dp[i][k][j], 
                                    max(dp[i-1][k][t-1] + t, dp[i][t+1][j] + t));
            }
}

int main() {
    init();
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &k, &m);
        printf("%d\n", dp[k][1][m]);
    }
    return 0;
}