编辑代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

const int MAXN = 9999; // 假设的最大值
const int MAXK = 9999;  // 假设的最大值

// 初始化三维动态规划数组,所有值设为-1
std::vector<std::vector<std::vector<int>>> dp(MAXN, std::vector<std::vector<int>>(MAXK, std::vector<int>(MAXN, -1)));

int solve(int n, int k, int f) {
    // 检查边界情况
    if (k == 0 || k > n) return INT_MAX;
    if (f == 0 || f == n) return 0; // 没有更多的测试或者已经测试了所有人

    // 如果已经计算过,直接返回结果
    if (dp[n][k][f] != -1) return dp[n][k][f];

    int minTests = INT_MAX;
    // 尝试所有可能的测试对象f
    for (int x = 1; x <= f; ++x) {
        // 计算剩余未测试的人需要的最小测试次数
        int remainingTests = std::min(solve(n - x, k - 1, f - x), solve(n - x, k, x - 1));
        minTests = std::min(minTests, remainingTests + 1); // 选择最小测试次数加当前测试f
    }

    // 存储结果并返回
    dp[n][k][f] = minTests;
    return minTests;
}

int main() {
    int n, k;
    std::cin >> n >> k; // 从用户那里获取n和k的值

    // 检查n和k是否在合理的范围内
    if (n < 1 || n > MAXN || k < 1 || k > MAXK) {
        std::cerr << "输入的n或k超出了预设的范围。" << std::endl;
        return 1;
    }

    // 计算并输出结果
    std::cout << "Minimum number of tests required: " << solve(n, k, n - 1) << std::endl;

    return 0;
}