P1504 积木城堡

网页链接

P1504 积木城堡

题目描述

XC 的儿子小 XC 最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。

小 XC 是一个比他爸爸 XC 还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大或者下面的积木和上面的积木一样大，那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。

小 XC 想把自己垒的城堡送给幼儿园里漂亮的女孩子们，这样可以增加他的好感度。为了公平起见，他决定送给每个女孩子一样高的城堡，这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。

可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。

任务：

请你帮助小 XC 编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。

注意：一座城堡的高度，是组成它的所有积木的棱长之和。

输入格式

第一行是一个整数n nn，表示一共有n nn座城堡。

以下n nn行每行是一系列非负整数，用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。

输出格式

一个整数，表示最后城堡的最大可能的高度。
如果找不到合适的方案，则输出0 00。

输入输出样例 #1

输入 #1

2 2 1 -1 3 2 1 -1

输出 #1

3

说明/提示

【数据范围】
对于100 % 100\%100%的数据，1 ≤ n ≤ 100 1 \le n \le 1001≤n≤100，一座城堡中的积木不超过100 100100块，每块积木的棱长不超过100 100100。

解题思路

本题是多组01背包可行性 + 公共最大子集和的经典问题，核心是对每座城堡独立计算所有可达到的剩余高度，再找出所有城堡共有的最大高度。

1. 问题等价转化

每座城堡可以移除任意数量的积木，剩余积木保持原有上下顺序，天然满足下大上小的堆叠规则。因此剩余高度等价于从该城堡积木中选取一个子集的棱长之和。问题最终转化为：

求所有城堡都能凑出的最大子集和高度。

2. 单座城堡：01背包求可行高度

对每一座城堡，用01背包求解所有可以凑出的高度：

• 定义布尔数组f[j]，表示高度j是否可以由当前城堡的积木子集组成。
• 初始边界：f[0] = true，即不选任何积木时高度为0，一定可行。
• 状态转移：对每一块积木，从高到低倒序遍历高度，若j - 棱长可行，则j也可行。

3. 统计公共高度

用计数数组ans[j]记录有多少座城堡可以凑出高度j：

• 每处理完一座城堡，将该城堡所有可行高度对应的ans[j]加1。
• 同一座城堡中同一个高度只能计数一次，因此仅当f[j]从不可行变为可行时才执行计数加1，避免重复统计。

4. 求解最大公共高度

从所有城堡的最大总高度开始，从高到低遍历所有高度：

• 第一个满足ans[j] == n的高度，就是所有城堡都能达到的最大高度，直接输出。
• 若遍历完所有正高度都无满足条件的，输出0（对应全部移除积木的情况）。

复杂度分析

单座城堡最大高度不超过 100×100 = 10000，城堡总数不超过100，总运算量约为 10^7 级别，完全适配1秒时间限制。

总结

核心逻辑：将每座城堡的剩余高度问题转化为子集和可行性，通过01背包逐座计算可行高度，统计每个高度的覆盖城堡数，从高到低查找第一个全覆盖的高度即为答案。
关键操作：01背包可行性判定、单座高度去重计数、倒序遍历找最大值。
效率保障：单座背包运算量可控，整体复杂度线性叠加，无冗余计算。

代码简要说明

1. 全局变量：

   • n为城堡总数，maxn记录所有城堡的最大总高度，用于限定遍历上界。
   • a数组暂存当前城堡的积木棱长，g为当前城堡积木数量，sum为当前城堡总高度。
   • f为当前城堡的可行性数组，ans数组统计每个高度被多少座城堡覆盖。

2. 逐座城堡处理：

   • 每座城堡开始前重置f数组为全0，初始化f[0] = true。
   • 循环读取积木棱长，直到遇到-1结束，同步累加总高度与积木数。
   • 执行01背包倒序转移：若j-a[i]可行且j尚未标记为可行，则标记j为可行，并将ans[j]计数加1，保证单座城堡同一高度仅计数一次。

3. 查找答案：
   从maxn到0倒序遍历高度，第一个计数等于城堡总数的高度即为答案，直接输出并结束程序；若未找到则输出0。

4. 输入优化：关闭流同步并解绑tie，提升多组数据的读取效率。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,maxn,x,g,sum;ll a[1001],ans[100001];boolf[100001];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(ll k=1;k<=n;k++){memset(f,0,sizeof(f));g=0;sum=0;while(1){cin>>x;if(x<0)break;a[++g]=x;sum+=x;}f[0]=1;a[0]=g;if(sum>maxn)maxn=sum;for(ll i=1;i<=g;i++){for(ll j=sum;j>=a[i];j--)if(f[j-a[i]]&&!f[j]){f[j]=1;ans[j]++;}}}for(ll i=maxn;i>=0;i--){if(ans[i]==n){cout<<i;return0;}}cout<<0;return0;}