P1504 积木城堡【洛谷算法习题】

P1504 积木城堡网页链接P1504 积木城堡题目描述XC 的儿子小 XC 最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的城堡的每一层是一块积木。小 XC 是一个比他爸爸 XC 还聪明的孩子他发现垒城堡的时候如果下面的积木比上面的积木大或者下面的积木和上面的积木一样大那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。小 XC 想把自己垒的城堡送给幼儿园里漂亮的女孩子们这样可以增加他的好感度。为了公平起见他决定送给每个女孩子一样高的城堡这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了他灵机一动想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木使得最终每座城堡都一样高。为了使他的城堡更雄伟他觉得应该使最后的城堡都尽可能的高。任务请你帮助小 XC 编一个程序根据他垒的所有城堡的信息决定应该移去哪些积木才能获得最佳的效果。注意一座城堡的高度是组成它的所有积木的棱长之和。输入格式第一行是一个整数n nn表示一共有n nn座城堡。以下n nn行每行是一系列非负整数用一个空格分隔按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。输出格式一个整数表示最后城堡的最大可能的高度。如果找不到合适的方案则输出0 00。输入输出样例 #1输入 #12 2 1 -1 3 2 1 -1输出 #13说明/提示【数据范围】对于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背包可行性判定、单座高度去重计数、倒序遍历找最大值。效率保障单座背包运算量可控整体复杂度线性叠加无冗余计算。代码简要说明全局变量n为城堡总数maxn记录所有城堡的最大总高度用于限定遍历上界。a数组暂存当前城堡的积木棱长g为当前城堡积木数量sum为当前城堡总高度。f为当前城堡的可行性数组ans数组统计每个高度被多少座城堡覆盖。逐座城堡处理每座城堡开始前重置f数组为全0初始化f[0] true。循环读取积木棱长直到遇到-1结束同步累加总高度与积木数。执行01背包倒序转移若j-a[i]可行且j尚未标记为可行则标记j为可行并将ans[j]计数加1保证单座城堡同一高度仅计数一次。查找答案从maxn到0倒序遍历高度第一个计数等于城堡总数的高度即为答案直接输出并结束程序若未找到则输出0。输入优化关闭流同步并解绑tie提升多组数据的读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;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);cinn;for(ll k1;kn;k){memset(f,0,sizeof(f));g0;sum0;while(1){cinx;if(x0)break;a[g]x;sumx;}f[0]1;a[0]g;if(summaxn)maxnsum;for(ll i1;ig;i){for(ll jsum;ja[i];j--)if(f[j-a[i]]!f[j]){f[j]1;ans[j];}}}for(ll imaxn;i0;i--){if(ans[i]n){couti;return0;}}cout0;return0;}