A5650 | $「CSP-S 2024」染色$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

给定一个长度为 $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 \limits_{i=1}^n C_i$。你需要最大化最终得分，请求出最终得分的最大值。

从文件 color.in 中读入数据。 **本题有多组测试数据。** 输入的第一行包含一个正整数 $T$，表示数据组数。 接下来包含 $T$ 组数据，每组数据的格式如下： 第一行包含一个正整数 $n$，表示数组长度。 第二行包含 $n$ 个正整数 $A_1, A_2, \dots, A_n$，表示数组 $A$ 中的元素。

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

输入 #1

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

输出 #1

1
0
8

C++ 编辑器

输入

输出