Bribing Friends

题目描述

Bessie 想去看《Bovine Genomics: The Documentary》，但她不想一个人去。不幸的是，她的朋友们对和她一起去并不够热情！因此，Bessie 需要贿赂她的朋友们陪她去电影院。她的贿赂手段有两种：mooney 和冰淇淋蛋筒。

Bessie 有 $N$（$1 \le N \le 2000$）个朋友。然而，并不是所有朋友都一样！朋友 $i$ 的人气值为 $P_i$（$1 \le P_i \le 2000$），而 Bessie 希望最大化陪她一起去的朋友的人气值之和。朋友 $i$ 只有在 Bessie 给他 $C_i$（$1 \le C_i \le 2000$）个 mooney 时才愿意陪她一起去。如果 Bessie 给他 $X_i$（$1 \le X_i \le 2000$）个冰淇淋蛋筒，他还会给 Bessie 提供 $1$ 个 mooney 的折扣。对于同一个朋友，只要这些折扣不会导致该朋友反过来给 Bessie mooney，Bessie 就可以从该朋友那里获得任意多个整数折扣。

Bessie 手头有 $A$ 个 mooney 和 $B$ 个冰淇淋蛋筒（$0 \le A, B \le 2000$）。请你帮助她在最优使用 mooney 与冰淇淋蛋筒的情况下，确定她所能达到的人气值总和的最大值！

输入格式

第 $1$ 行包含三个数 $N$、$A$ 和 $B$，分别表示朋友数量、Bessie 拥有的 mooney 数量以及冰淇淋蛋筒数量。

接下来 $N$ 行每行包含三个数 $P_i$、$C_i$ 和 $X_i$，分别表示人气值（$P_i$）、贿赂朋友 $i$ 陪 Bessie 所需的 mooney 数量（$C_i$），以及从朋友 $i$ 获得 $1$ 个 mooney 折扣所需的冰淇淋蛋筒数量（$X_i$）。

输出格式

输出在 Bessie 最优使用 mooney 和冰淇淋蛋筒的情况下，陪她一起去的朋友的人气值总和的最大值。

3 10 8
5 5 4
6 7 3
10 6 3

15

提示

Bessie 可以给第 $1$ 头牛 $4$ 个 mooney 和 $4$ 个冰淇淋蛋筒，并给第 $3$ 头牛 $6$ 个 mooney 和 $3$ 个冰淇淋蛋筒，从而让第 $1$ 头牛和第 $3$ 头牛陪她一起去，总人气为 $5 + 10 = 15$。

评分： 测试点 2-4 满足 $N \leq 5$ 且 $C_i = 1$ 测试点 5-7 满足 $B = 0$ 测试点 8-10 满足 $N, A, B, P_i, C_i, X_i \leq 50$ 测试点 11-15 满足 $N, A, B, P_i, C_i, X_i \leq 200$ 测试点 16-20 无额外限制 题目致谢：Timothy Feng, Nathan Wang, and Sam Zhang

标签: USACO|2022|Gold

来源

USACO|2022|Gold