挂钩's trick

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

有

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 处记录了。

CPP

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

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

文章操作