CF2244G Yura and Deadlines

Yura 有 $n$ 个作业。每个作业的权重 $a_i$ 已知——如果 Yura 完成该作业，将获得的课程分数。 Yura 希望选择一个作业的子集，使他获得的总分最大。但是，他遇到了一个问题：有些作业太耗时间了。如果 Yura 同时完成第 $i$ 个和第 $j$ 个作业（$i \neq j$），那么它们之间必须有足够多的其他作业，否则他会分心，无法完成它们。 具体地，对于任意两个被选中的作业，其下标为 $i$ 和 $j$，必须满足条件：$|i-j| > \max(a_i, a_j)$。 请你求出 Yura 在满足上述条件的前提下，最多能获得多少分。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的个数。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$），表示数组的各个元素。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示所选作业的最大总分。

在第一个样例中，最优方案是选择下标为 $1$ 和 $5$ 的作业。 在第三个样例中，最优方案是选择下标为 $1$ 和 $6$ 的作业。 由 ChatGPT 5 翻译