猿宝猜数字

#include <bits/stdc++.h>
using namespace std;

int n, m, dp[305][305][25];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][i][j] = 0;
            dp[i][i - 1][j] = 0;
        }
    }
    for (int t = 0; t <= m; t++) { //用了几次机会
        for (int i = n; i >= 1; i--) { //L
            for (int j = i + 1; j <= n; j++) { //R
                dp[i][j][t] = 0x3f3f3f3f;
                for (int k = i; k <= j; k++) { //猜k
                    int tmp1 = max(dp[i][k - 1][t], dp[k + 1][j][t]) + k;
                    dp[i][j][t] = min(dp[i][j][t], tmp1);
                    if (t) {
                        int tmp2 = max(dp[i][k - 1][t - 1], dp[k + 1][j][t - 1]);
                        dp[i][j][t] = min(dp[i][j][t], tmp2);
                    }
                    
                }
            }
        }
    }
    printf("%d\n", dp[1][n][m]);

    return 0;
}