本文共 1887 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要找到一种方法来使用K枚鱼肉炸弹，使得每个楼被看守的猫的数量Si中的最大值尽可能小。我们可以通过构建伪二叉树并使用动态规划来解决这个问题。

方法思路

解决代码

#include 
   
    #include 
    
     using namespace std;long long n, k, BOSS, h[1000005], c[1000005], b[1000005], f[1000005][6];struct node {    long long l, r;} a[1000005];long long maketree(long long l, long long r) {    if (l > r) return 0;    if (l == r) return l;    long long o = 0, mid = 0;    for (long long i = l; i <= r; ++i) {        if (h[i] > o) {            o = h[i];            mid = i;        }    }    a[mid].l = maketree(l, mid - 1);    a[mid].r = maketree(mid + 1, r);    return mid;}void dfs(long long x) {    b[x] = 1;    if (a[x].l != 0 && !b[a[x].l]) dfs(a[x].l);    if (a[x].r != 0 && !b[a[x].r]) dfs(a[x].r);    for (long long i = 0; i <= k; ++i) {        for (long long j = 0; j <= k - i; ++j) {            if (i + j < k) {                f[x][i + j] = min(f[x][i + j], max(f[a[x].l][i], f[a[x].r][j]) + c[x]);                if (f[x][i + j + 1] > max(f[x][i + j + 1], max(f[a[x].l][i], f[a[x].r][j]) + c[x])) {                    f[x][i + j + 1] = max(f[x][i + j + 1], max(f[a[x].l][i], f[a[x].r][j]) + c[x]);                }            } else {                f[x][i + j] = max(f[x][i + j], max(f[a[x].l][i], f[a[x].r][j]) + c[x]);            }        }    }}int main() {    memset(f, 0x3f, sizeof(f));    f[0][0] = 0;    scanf("%lld%lld", &n, &k);    for (long long i = 1; i <= n; ++i) {        scanf("%lld%lld", &h[i], &c[i]);    }    BOSS = maketree(1, n);    dfs(BOSS);    cout << f[BOSS][k] << endl;}
    
   

代码解释

通过这种方法，我们可以在给定的K枚炸弹中找到使Si的最大值最小的方案。