题意理解
有 nnn 座城堡,每座由若干积木组成,高度为积木棱长之和。现在要从每座城堡中移除一些积木,使得所有城堡高度相同。求最大可能的高度。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
对于每座城堡,需要判断它能达到哪些高度。这是一个01背包问题:选择若干积木,使得总和恰好为某个值。
设 dp[j]dp[j]dp[j] 表示当前城堡能否达到高度 jjj。
做法:
1. 对每座城堡做一次 01 背包,求出它能达到的所有高度
2. 用 cnt[j]cnt[j]cnt[j] 统计有多少座城堡能达到高度 jjj
3. 找出所有 nnn 座城堡都能达到的最大高度
边界条件:
* dp[0]=truedp[0] = truedp[0]=true:高度为 0 一定可以达到(不选任何积木)
答案: cnt[j]=ncnt[j] = ncnt[j]=n 的最大 jjj
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码