解题思路

• 这是一个二维约束的 0/1 背包问题：每个朋友是一件物品，消耗时间 ti 与脑细胞 hi，价值为点赞数 ai；总时间不超过 T、总脑细胞不超过 H，问最大点赞数。

• 动态规划（二维 0/1 背包） 设 dp[t][h] 表示在时间上限为 t、脑细胞上限为 h 时能获得的最大点赞数。 对每个朋友进行一次倒序转移：

  dp[t][h] = max(dp[t][h], dp[t - ti][h - hi] + ai)   (t>=ti 且 h>=hi)

题目内容

小朱同学看到小红书上有很多外国人涌入，于是决定给这些外国人展示他与朋友们的日常生活。

已知他有 $n$ 个朋友，分享他第 $i$ 个朋友的故事需要花费 $Ti$ 的时间和 $Hi$ 的脑细胞来编辑文章，并在发表后能获得 $Ai$ 的点赞量。

请问:在花费总时间不超过 $T$ 且总脑细胞不超过 $H$ 的前提下，最多可以获得多少点赞量?

提示:$1<=n<=100$

$1<=H、T、ti、hi、 ai<=100$

输入描述

第一行输入一个正整数 $n$ ，代表朋友的数量。

第二行输入两个正整数 $T$ 和 $H$ ，代表时间限制和脑细胞限制(脑细胞不会重生)。空格隔开

接下来的 $n$ 行，每行输入三个正整数 $ti,hi,ai$，代表分享第 $i$ 个朋友的故事需要花费 $ti$ 的时间、$hi$ 的脑细胞，然后能获得 $ai$ 的点赞量，空格隔开。

输出描述

最多可以获得的点赞量

样例1

输入

2
5 4
1 5 2
6 2 3

输出

0

说明

时间或脑细胞无法完成任何一项创作，故获得 $0$ 点赞量

样例2

输入

3
5 4
1 2 2
2 1 3
4 1 5

输出

7

说明

在不超过限制的情况下，分享第 $1$ 个和第 $3$ 个朋友的故事可获得的点赞量最高，为 $7$