跳至正文
#618

染色

NOI/NOI+/CTSC
查看题目操作

染色

题目描述

给定一个长度为 n 的正整数数组 A,其中所有数从左至右排成一排。 你需要将 A 中的每个数染成红色或蓝色之一,然后按如下方式计算最终得分: 设 C 为长度为 n 的整数数组,对于 A 中的每个数 Ai(1 ≤ i ≤ n): • 如果 Ai 左侧没有与其同色的数,则令 Ci = 0。 • 否则,记其左侧与其最靠近的同色数为 Aj,若 Ai = Aj,则令 Ci = Ai,否则令 Ci = 0。 你的最终得分为 C 中所有整数的和,即∑i=1nCi\sum _ { i = 1 } ^ { n } C _ { i }。你需要最大化最终得分,请求出最终得分的最大值

输入格式

从标准输入读入数据。 本题有多组测试数据。 输入的第一行包含一个正整数 T,表示数据组数。 接下来包含 T 组数据,每组数据的格式如下: 第一行包含一个正整数 n,表示数组长度。 第二行包含 n 个正整数 A1, A2, . . . , An,表示数组 A 中的元素。

输出格式

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

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

提示

【样例 1 解释】

第一组数组是 [1,2,1][1,2,1]。若把前两个数染红、第三个数染蓝,得分为 00;若三个数全部染红,得分同样为 00,因为相邻的同色数都不相等。把第一个和第三个数染红、第二个数染蓝时,第三个数贡献 11,总得分为 11,这也是最大值。

第二组的元素两两不同,因此任意染色方案的得分都为 00。

第三组可将位置 1,2,4,5,71,2,4,5,7 染红,位置 3,6,83,6,8 染蓝。对应贡献为 [0,0,0,5,0,2,1,0][0,0,0,5,0,2,1,0],总得分为 88。

【样例 2】 见选手目录下的 color/color2.in 与 color/color2.ans。 【数据范围】 对于所有测试数据,保证:1 ≤ T ≤ 10,2 ≤ n ≤ 2 × 105,1 ≤ Ai ≤ 106。

来源

CSP-J/S 2024 第二轮认证 提高级