[ABC364E] Maximum Glutton 讲解

· · 题解

[ABC364E] Maximum Glutton

题目考察：dp，背包。
题目简述：
有 n 个物品，拥有第 i 个物品需要花费 a_i 的 A 代价，b_i 的 B 代价。在满足 A 代价不超过 x，B 代价不超过 y 的基础上，他会继续选择下一个物品。直到 A 代价大于 x 或 B 代价大于 y。求最多拥有多少件物品。
数据范围：

暴力 dp 的话，设状态 f_{i,j,k} 为选择到第 i 个物品，花费了 j 的 A 代价和 k 的 B 代价所能选择的最大物品数量，则转移方程为：

f_{i,j,k}=\max(f_{i-1,j,k},f_{i-1,j-a_i,k-b_i}+1)

但时间复杂度为 \Theta(nxy)，这样即使压去第一维也无法通过。

我们注意到他最多选 n 个物品，价值非常小。那么设 f_{i,j,k} 为选到第 i 个物品，A 代价花费了 j，选出了 k 个物品所花费的最小 B 代价，那么这样得到状态转移方程：

f_{i,j,k}=\min(f_{i-1,j,k},f_{i-1,j-a_i,k-1}+b_i)

最后的时候我们压去第一维，这样时间复杂度为 \Theta(n^2x)，空间复杂度为 \Theta(nx)，可以通过。

代码