← 返回题目列表

Codeforces · 1800/C1

C1. 为英雄提供动力(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。它与困难的区别仅在于对 $$$n$$$ 和 $$$t$$$ 的约束。

有一副 $$$n$$$ 牌,每张牌都有其威力。卡有两种类型:

- 英雄卡牌,该卡牌的力量始终等于$$$0$$$;
- 一张奖励卡,此类卡的威力始终为正。

您可以对牌组执行以下操作:

- 从牌堆顶取出一张牌;
- 如果这张卡是奖励卡,你可以将其放在你的奖励卡组顶部或丢弃;
- 如果这张卡是英雄卡,那么你的奖励卡组顶牌的力量将被添加到他的力量中(如果它不为空),之后该英雄被添加到你的军队中,并且使用的奖励被丢弃。

你的任务是通过这些行动来聚集一支拥有最大可能总力量的军队。

输入

输入数据的第一行包含单个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试中的测试用例数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 一副牌中的牌数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \dots, s_n$$$ ($$$0 \le s_i \le 10^9$$$) - 卡牌能力按自上而下的顺序排列。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

输出$$$t$$$个数字,每个数字都是相应测试用例的答案——军队可以达到的最大可能总战力。

示例

输入 #1

5
5
3 3 3 0 0
6
0 3 3 0 0 3
7
1 2 3 0 4 5 0
7
1 2 5 0 4 3 0
5
3 1 0 0 4

输出 #1

6
6
8
9
4

注意

在第一个示例中,您可以获得奖金 $$$1$$$ 和 $$$2$$$。两张英雄卡都将获得 $$$3$$$ 力量。如果您拿走所有奖金,其中一项将保持未使用状态。

在第二个示例中,牌组顶部的英雄卡牌无法启动,其余的可以通过 $$$2$$$ 和 $$$3$$$ 奖励进行启动并获得 $$$6$$$ 总能量。

在第四个示例中,您可以获取奖金$$$1$$$、$$$2$$$、$$$3$$$、$$$5$$$并跳过奖金$$$6$$$,然后英雄$$$4$$$将获得$$$3$$$的奖金$$$5$$$的增强,而英雄$$$7$$$将获得$$$5$$$的奖金$$$5$$$的增强$$$4$$$。 $$$4+5=9$$$。