本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-03 11:55:20

[ABC364E] Maximum Glutton

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

• $1\le n\le 80$
• $1\le x,y\le 10^4$
• $\forall i\in[1,n],1\le a_i,b_i\le 10^4$

首先我们设在 A 代价不超过 $x$，B 代价不超过 $y$ 的情况下最多选 $tmp$ 个物品，则最终可以选择 $\min(n,tmp+1)$ 个物品。

暴力 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)$，可以通过。

代码