挂钩's trick

VitrelosTia · 2025-08-20 10:49:43 · 个人记录

名字是我乱取的。来源。为什么是挂饰啊w，不管了。

ABC219D

有 n 个物品，每个物品能获得 a_i 个 A，b_i 个 B，给定 x,y，问最少物品数使得 \sum a \ge x 且 \sum b \ge y。

设 f_{i,a,b} 表示考虑前 i 个物品，获得了 \ge a 个 A，\ge b 个 B，转移的时候后面的两维和 0 取 max，事实上相当于把负数下标在 0 处记录了。

memset(f, 0x3f, sizeof f); f[0][0][0] = 0;
f[i][j][k] = min(f[i - 1][j][k], f[i - 1][max(j - a[i], 0ll)][max(k - b[i], 0ll)] + 1);

面对这种 \ge 型的背包问题，通过这种状态设计能在保证时空复杂度的情况下计算答案。