#P3. [CSP-S 2024] Red and blue array

[CSP-S 2024] Red and blue array

题目描述

给定一个长度为 nn 的正整数数组 AA,其中所有数从左至右排成一排。

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

CC 为长度为 nn 的整数数组,对于 AA 中的每个数 AiA_i1in1 \leq i \leq n):

  • 如果 AiA_i 左侧没有与其同色的数,则令 Ci=0C_i = 0
  • 否则,记其左侧与其最靠近的同色数AjA_j,若 Ai=AjA_i = A_j,则令 Ci=AiC_i = A_i,否则令 Ci=0C_i = 0

你的最终得分为 CC 中所有整数的和,即 i=1nCi\sum \limits_{i=1}^n C_i。你需要最大化最终得分,请求出最终得分的最大值。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 TT,表示数据组数。

接下来包含 TT 组数据,每组数据的格式如下:

第一行包含一个正整数 nn,表示数组长度。

第二行包含 nn 个正整数 A1,A2,,AnA_1, A_2, \dots, A_n,表示数组 AA 中的元素。

输出格式

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

样例

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

提示

【样例 1 解释】

对于第一组数据,以下为三种可能的染色方案:

  1. A1,A2A_1, A_2 染成红色,将 A3A_3 染成蓝色(121\red{1}\red{2}\blue{1}),其得分计算方式如下:
  • 对于 A1A_1,由于其左侧没有红色的数,所以 C1=0C_1 = 0
  • 对于 A2A_2,其左侧与其最靠近的红色数为 A1A_1。由于 A1A2A_1 \neq A_2,所以 C2=0C_2 = 0
  • 对于 A3A_3,由于其左侧没有蓝色的数,所以 C3=0C_3 = 0
    该方案最终得分为 C1+C2+C3=0C_1 + C_2 + C_3 = 0
  1. A1,A2,A3A_1, A_2, A_3 全部染成红色(121\red{121}),其得分计算方式如下:
  • 对于 A1A_1,由于其左侧没有红色的数,所以 C1=0C_1 = 0
  • 对于 A2A_2,其左侧与其最靠近的红色数为 A1A_1。由于 A1A2A_1 \neq A_2,所以 C2=0C_2 = 0
  • 对于 A3A_3,其左侧与其最靠近的红色数为 A2A_2。由于 A2A3A_2 \neq A_3,所以 C3=0C_3 = 0
    该方案最终得分为 C1+C2+C3=0C_1 + C_2 + C_3 = 0
  1. A1,A3A_1, A_3 染成红色,将 A2A_2 染成蓝色(121\red{1}\blue{2}\red{1}),其得分计算方式如下:
  • 对于 A1A_1,由于其左侧没有红色的数,所以 C1=0C_1 = 0
  • 对于 A2A_2,由于其左侧没有蓝色的数,所以 C2=0C_2 = 0
  • 对于 A3A_3,其左侧与其最靠近的红色数为 A1A_1。由于 A1=A3A_1 = A_3,所以 C3=A3=1C_3 = A_3 = 1
    该方案最终得分为 C1+C2+C3=1C_1 + C_2 + C_3 = 1

可以证明,没有染色方案使得最终得分大于 11

对于第二组数据,可以证明,任何染色方案的最终得分都是 00

对于第三组数据,一种最优的染色方案为将 A1,A2,A4,A5,A7A_1, A_2, A_4, A_5, A_7 染为红色,将 A3,A6,A8A_3, A_6, A_8 染为蓝色(35251214\red{35}\blue{2}\red{51}\blue{2}\red{1}\blue{4}),其对应 C=[0,0,0,5,0,1,2,0]C = [0, 0, 0, 5, 0, 1, 2, 0],最终得分为 88

【样例 2】

见选手目录下的 color/color2.in 与 color/color2.ans。

【数据范围】

对于所有测试数据,保证:1T101\leq T\leq 102n2×1052\leq n\leq 2\times 10^51Ai1061\leq A_i\leq 10^6

测试点 nn AiA_i
141\sim 4 15\leq 15
575\sim 7 102\leq 10^2
8108\sim 10 2000\leq 2000
11,1211,12 2×104\leq 2\times 10^4 106\leq 10^6
131513\sim 15 2×105\leq 2\times 10^5 10\leq 10
162016\sim 20 106\leq 10^6