YLT C++ 4级 2021.03

N5497 [CIE 202103 四级 T1] 酒鬼

题目描述

$Santo$ 刚刚与房东打赌赢得了一间在 $New$ $Clondike$ 的大客厅。今天，他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令 $Santo$ 高兴的是，瓶子中的酒都有不同的味道。房东说道：“你可以喝尽可能多的酒，但是一旦打开酒盖你就必须把它喝完，喝完一瓶后把它放回原处。还有一件最重要的事，你必须从左至右依次喝，并且不能连续超过三瓶，不然会给你带来坏运气。”现在可怜的 $Santo$ 站在酒吧前努力的想着，他到底应该喝哪几瓶才能使喝的酒最多呢？请帮助他找出他应该喝的酒瓶号，因为思考让他感到不安。

输入格式

第一行一个整数 $N$,有 $N$ 个酒瓶。$N\leq 700$ 接下有 $N$ 行，第 $I+1$ 行的数字代表酒瓶 $I$ 中酒的体积。

输出格式

一个数字，喝的酒的最大总体积。遵守以上规则，使得三个连续瓶子中至少一个瓶子是满的。

样例

样例 1
输入：

6
6
10
13
9
8
1

输出：

33

提示

无

N5498 [CIE 202103 四级 T2] 重启系统

题目描述

小明帮助管理一个处理数据的计算系统，有 $N$ 个待处理的任务，需要按照顺序来完成这些任务，即每次所完成任务的编号都要大于前一个完成任务的编号，且单个任务不可以分解完成。计算系统运行着一个奇怪的保护程序，它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。重启系统可以使它立刻恢复到最高性能（一开始系统拥有最高性能，最高性能大于任何待处理任务的数据量）。小明有一次重启系统的权限（也可以不使用），你能帮他算出最多能完成几个任务吗？

输入格式

第一行： $N$ $(2 \leq N \leq 1000)$ 待处理的任务数 第二行： $N$ 个整数，每个任务的数据量

输出格式

输出只包括一行，这一行只包含一个整数，表示最多能完成的任务数。

样例

样例 1
输入：

10
1 5 4 3 2 10 9 8 7 6

输出：

9

提示

回想一下最长上升子序列问题

N5499 [CIE 202103 四级 T3] 鸣人的影分身

题目描述

在火影忍者的世界里，令敌人捉摸不透是非常关键的。我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。
针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
那么问题来了，假设鸣人的查克拉能量为 $M$，他影分身的个数为 $N$，那么制造影分身时有多少种（用 $K$ 表示）不同的分配方法？（影分身可以被分配到 $0$ 点查克拉能量）

输入格式

第一行是测试数据的数目 $t$ $(0 \leq t \leq 20)$。以下每行均包含二个整数 $M$ 和 $N$，以空格分开。$1 \leq M,N \leq 10$。

输出格式

对输入的每组数据 $M$ 和 $N$，用一行输出相应的 $K$。

样例

样例 1
输入：

1
7 3

输出：

8

提示

无

N5500 [CIE 202103 四级 T4] 宠物小精灵之收服

题目描述

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。当皮卡丘的体力小于等于 $0$ 时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于 $0$ 的野生小精灵也不会被小智收服。当小智的精灵球用完时，狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入格式

输入数据的第一行包含三个整数：$N(0 < N < 1000)$，$M(0 < M < 500)$，$K(0 < K < 100)$，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的 $K$ 行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出格式

输出为一行，包含两个整数：$C$，$R$，分别表示最多收服 $C$ 个小精灵，以及收服 $C$ 个小精灵时皮卡丘的剩余体力值最多为 $R$。

样例

样例 1
输入：

10 100 5
7 10
2 40
2 50
1 20
4 20

输出：

3 30

样例 2
输入：

10 100 5
8 110
12 10
20 10
5 200
1 110

输出：

0 100

提示

对于样例输入 $1$：小智选择：$(7,10)$ $(2,40)$ $(1,20)$ 这样小智一共收服了 $3$ 个小精灵，皮卡丘受到了 $70$ 点伤害，剩余 $100-70=30$ 点体力。所以输出 $3$ $30$
对于样例输入 $2$：小智一个小精灵都没法收服，皮卡丘也不会收到任何伤害，所以输出 $0$ $100$