主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
挂钩's trick
最后更新于 2025-08-27 17:42:39
作者
VitrelosTia
分类
个人记录
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
名字是我乱取的。[来源](https://www.luogu.com.cn/discuss/989432)。 [ABC219D](https://www.luogu.com.cn/problem/AT_abc219_d) 有 $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$ 型的背包问题，通过这种状态设计能在保证时空复杂度的情况下计算答案。
正在渲染内容...
点赞
0
收藏
0
