题目详情题解（0）讨论（0）提交记录（0）

CF1974E.Money Buys Happiness

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

作为一名物理学家，Charlie 喜欢以简单而精确的方式规划自己的生活。

在接下来的 mm 个月里，Charlie 从零开始，每月努力工作并赚取 xx 英镑。在第 ii 个月（1≤i≤m1 \le i \le m），他有一次机会花费 cic_i 英镑来获得 hih_i 的幸福值。

不允许借钱。在第 ii 个月赚到的钱只能在之后的第 jj 个月（j>ij>i）花费。

由于物理学家不会编程，请你帮 Charlie 求出他能获得的最大幸福值总和。

输入格式

输入的第一行包含一个整数 tt（1≤t≤10001 \le t \le 1000），表示测试用例的数量。

每个测试用例的第一行包含两个整数 mm 和 xx（1≤m≤501 \le m \le 50，1≤x≤1081 \le x \le 10^8），分别表示总月数和每月工资。

接下来的 mm 行中，第 ii 行包含两个整数 cic_i 和 hih_i（0≤ci≤1080 \le c_i \le 10^8，1≤hi≤1031 \le h_i \le 10^3），分别表示第 ii 个月的花费和可获得的幸福值。注意，有些幸福值可能是免费的（即某些 ci=0c_i=0）。

保证所有测试用例中 ∑ihi\sum_i h_i 的总和不超过 10510^5。

输出格式

对于每个测试用例，输出一个整数，表示 Charlie 能获得的最大幸福值总和。

输入输出样例

  • 输入#1

    7
1 10
1 5
2 80
0 10
200 100
3 100
70 100
100 200
150 150
5 8
3 1
5 3
3 4
1 5
5 3
2 5
1 5
2 1
5 3
2 5
2 4
4 1
5 1
3 4
5 2
2 1
1 2
3 5
3 2
3 2

    输出#1

    0
10
200
15
1
9
9

说明/提示

在第一个测试用例中，Charlie 只在月末拿到工资，因此无法购买任何东西。

在第二个测试用例中，Charlie 在第一个月获得了免费的幸福值。

在第三个测试用例中，最优策略是在第二个月购买幸福值。即使最后还有剩余的钱，Charlie 也无法回到过去获得第一个月的幸福值。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页