题意理解
有 NNN 种方块,第 iii 种高度 hih_ihi ,数量 cic_ici ,且使用时顶部高度不能超过 aia_iai 。求能堆出的最大高度。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
这是带限制的多重背包问题。
关键点: 必须按高度限制 aia_iai 从小到大排序后处理。因为限制小的方块必须放在下面,否则后面无法再放它。
设 dp[j]dp[j]dp[j] 表示高度 jjj 是否可达。
状态转移(多重背包):
对于每种方块(排序后),枚举使用的数量 kkk(1≤k≤ci1 \leq k \leq c_i1≤k≤ci ):
dp[j]=dp[j] or dp[j−hi]dp[j] = dp[j] \text{ or } dp[j - h_i] dp[j]=dp[j] or dp[j−hi ]
转移时需满足 j≤aij \leq a_ij≤ai (高度限制)
边界条件:
* dp[0]=truedp[0] = truedp[0]=true:高度 0 可达
答案: dp[j]=truedp[j] = truedp[j]=true 的最大 jjj
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码