题意理解

有 $n$ 座城堡，每座由若干积木组成，高度为积木棱长之和。现在要从每座城堡中移除一些积木，使得所有城堡高度相同。求最大可能的高度。

---

思路分析

对于每座城堡，需要判断它能达到哪些高度。这是一个01背包问题：选择若干积木，使得总和恰好为某个值。

设 $dp[j]$ 表示当前城堡能否达到高度 $j$。

做法：

1. 对每座城堡做一次 01 背包，求出它能达到的所有高度
2. 用 $cnt[j]$ 统计有多少座城堡能达到高度 $j$
3. 找出所有 $n$ 座城堡都能达到的最大高度

边界条件：

• $dp[0] = true$：高度为 0 一定可以达到（不选任何积木）

答案： $cnt[j] = n$ 的最大 $j$

---

参考代码

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

const int MAXH = 10005;  // 最大高度 100*100

int n;              // 城堡数量
int a[105];         // 当前城堡的积木
int cnt[MAXH];      // cnt[j]表示有多少座城堡能达到高度j
bool dp[MAXH];      // dp[j]表示当前城堡能否达到高度j

int main() {
    cin >> n;  // 读入城堡数量
    
    for (int i = 1; i <= n; i++) {  // 处理每座城堡
        int m = 0, sum = 0;  // m为积木数量，sum为总高度
        int x;
        while (cin >> x && x != -1) {  // 读入积木直到-1
            a[++m] = x;
            sum += x;
        }
        
        memset(dp, false, sizeof(dp));  // 初始化dp数组
        dp[0] = true;  // 边界：高度0一定可达
        
        for (int j = 1; j <= m; j++) {  // 01背包，枚举每块积木
            for (int k = sum; k >= a[j]; k--) {  // 逆序枚举高度
                if (dp[k - a[j]]) {  // 如果k-a[j]可达
                    dp[k] = true;  // 则k也可达
                }
            }
        }
        
        for (int j = 0; j <= sum; j++) {  // 统计当前城堡能达到的高度
            if (dp[j]) {
                cnt[j]++;  // 该高度可达的城堡数+1
            }
        }
    }
    
    int ans = 0;  // 答案
    for (int j = MAXH - 1; j >= 0; j--) {  // 从大到小找所有城堡都能达到的高度
        if (cnt[j] == n) {
            ans = j;
            break;
        }
    }
    
    cout << ans << endl;  // 输出答案
    return 0;
}