P1635 - [CSP-S 2024] 染色

内存限制：128 MB 时间限制：1.000 S

评测方式：文本比较命题人：

提交：1 解决：1

提交提交记录统计露一手!

给定一个长度为 $n$ 的正整数数组 $A$ ，其中所有数从左至右排成一排。

你需要将 $A$ 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：

设 $C$ 为长度为 $n$ 的整数数组，对于 $A$ 中的每个数 $A_{i}$ （ $1 \leq i \leq n$ ）：

如果 $A_{i}$ 左侧没有与其同色的数，则令 $C_{i} = 0$ 。
否则，记其左侧与其最靠近的同色数为 $A_{j}$ ，若 $A_{i} = A_{j}$ ，则令 $C_{i} = A_{i}$ ，否则令 $C_{i} = 0$ 。

你的最终得分为 $C$ 中所有整数的和，即 $\sum_{i = 1}^{n} C_{i}$ 。你需要最大化最终得分，请求出最终得分的最大值。

输入的第一行包含一个正整数 $T$ ，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含一个正整数 $n$ ，表示数组长度。

第二行包含 $n$ 个正整数 $A_{1}, A_{2}, \dots, A_{n}$ ，表示数组 $A$ 中的元素。

对于每组数据：输出一行包含一个非负整数，表示最终得分的最大可能值。

3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4

1
0
8

对于所有测试数据，保证： $1 \leq T \leq 10$ ， $2 \leq n \leq 2 \times 1 0^{5}$ ， $1 \leq A_{i} \leq 1 0^{6}$ 。

CSP-J 2024

提交提交记录统计露一手!

1635: [CSP-S 2024] 染色