积木城堡

题意

有 n 座城堡，每座城堡都是从下往上叠积木得到的。

如果想把某座城堡变矮，只能把最上面的若干块积木去掉；也就是说，最终能留下的高度一定是这座城堡的某个前缀和。

题目要求把所有城堡都改造成相同高度，并且这个高度尽量大。

这张表把题意翻成了前缀和模型：

原题对象	含义
一座城堡	一个前缀和集合
去掉最上面的积木	只能取前缀
所有城堡相同高度	求公共高度
高度尽量大	求最大公共值

思路

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#include <bits/stdc++.h>
using namespace std;

// 暴力做法：把每座城堡能保留的高度全部枚举出来，再取交集。
// 这能直接对应题意，适合小数据验证。

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> heights(n);
    for (int i = 0; i < n; i++) {
        int x, sum = 0;
        heights[i].push_back(0);
        while (cin >> x && x != -1) {
            sum += x;
            heights[i].push_back(sum);
        }
    }

    int answer = 0;
    for (int h : heights[0]) {
        bool ok = true;
        for (int i = 1; i < n && ok; i++) {
            if (!binary_search(heights[i].begin(), heights[i].end(), h)) {
                ok = false;
            }
        }
        if (ok) {
            answer = max(answer, h);
        }
    }

    cout << answer << '\n';

    return 0;
}

brute.cpp 先把每座城堡所有可能保留的高度都枚举出来，再判断这些高度是不是所有城堡都能达到。

这个做法正确，但不够高效，只适合小数据验证。

关键观察是：

每座城堡能留下的高度，只可能是它的前缀和。
题目要的是所有城堡共同能达到的最大高度。

于是我们只要统计每个高度被多少座城堡支持：

如果某个高度被 n 座城堡都支持，那它就是公共高度
从大到小找第一个公共高度，就是答案

这张表说明状态含义：

状态	含义
`cnt[h]`	高度 `h` 被多少座城堡支持

核心公式

设 $S_i$ 表示第 $i$ 座城堡所有可保留高度的集合。每个集合由前缀和构成：

S_i=\left\{\sum_{t=1}^{p} h_{i,t}\ \middle|\ 0\leqslant p\leqslant len_i\right\}

目标是求所有集合交集里的最大高度：

ans=\max\left(\bigcap_{i=1}^{n} S_i\right)

代码中用 $cnt_h$ 统计高度 $h$ 被多少座城堡支持，满足 $cnt_h=n$ 的最大 $h$ 就是答案。

公式解释：每座城堡能留下的高度正好是它从底部开始的前缀和。所有城堡高度相同，就是求这些前缀和集合的交集；统计出现次数可以快速判断某个高度是否属于所有集合。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#include <bits/stdc++.h>
using namespace std;

const int MAX_SUM = 10000 + 5;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> cnt(MAX_SUM, 0);
    int answer = 0;

    for (int i = 0; i < n; i++) {
        int x, sum = 0;
        while (cin >> x && x != -1) {
            sum += x;
            if (sum < MAX_SUM) {
                cnt[sum]++;
            }
        }
    }

    // 0 高度总是可行的；从高到低找第一个所有城堡都能达到的高度。
    for (int h = MAX_SUM - 1; h >= 1; h--) {
        if (cnt[h] == n) {
            answer = h;
            break;
        }
    }

    cout << answer << '\n';

    return 0;
}

复杂度

时间复杂度： $O(总积木数 + 最大高度)$
空间复杂度： $O(最大高度)$

总结

这题的核心不是复杂 DP，而是把“只能从上面删”翻译成“只能取前缀和”。

一旦得到每座城堡的前缀高度集合，问题就变成了：

求这些集合的最大交集元素

直接统计每个高度出现次数，是最稳妥也最容易写对的做法。

目录

题意

思路

核心公式

代码

复杂度

总结