g6-08110. 项目分包 · 林老师的题库

题目描述

动画工作室同时接了 $T$ 个外包项目，第 $i$ 个项目有一段总工时 $n$ 。每个项目要拆成若干个工作包，一个工作包恰好用掉 $k$ 个工时时能收到 $a_{k}$ 元报酬；所有工时必须全部用完，工作包不分先后。求每个项目最多能收到多少钱，按项目顺序每行输出一个数。

第一行一个整数 $T$ 。

接下来 $T$ 组数据，每组两行：第一行一个整数 $n$ ；第二行 $n$ 个整数 $a_{1}, a_{2}, \dots, a_{n}$ 。

输出 $T$ 行，每行一个整数，表示对应研究任务的最大总效益。

2
10
2 5 9 12 14 16 18 20 22 24
5
2 5 7 8 9

30
12

第一个项目把 10 个工时拆成 $3 + 3 + 4$ ，报酬 $9 + 9 + 12 = 30$ ；第二个项目拆成 $2 + 3$ ，报酬 $5 + 7 = 12$ 。

$1 \leq T \leq 5$ ， $1 \leq n \leq 1000$ ， $0 \leq a_{k} \leq 1 0^{4}$ 。保证答案在 64 位整数范围内。