[CSP-S 2024] 染色(color)
题目描述
给定一个长度为 n 的正整数数组 A,其中所有数从左至右排成一排。
你需要将 A 中的每个数染成红色或蓝色之一,然后按如下方式计算最终得分:
设 C 为长度为 n 的整数数组,对于 A 中的每个数 Ai(1≤i≤n):
- 如果 Ai 左侧没有与其同色的数,则令 Ci=0。
- 否则,记其左侧与其最靠近的同色数为 Aj,若 Ai=Aj,则令 Ci=Ai,否则令 Ci=0。
你的最终得分为 C 中所有整数的和,即 i=1∑nCi。你需要最大化最终得分,请求出最终得分的最大值。
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数 T,表示数据组数。
接下来包含 T 组数据,每组数据的格式如下:
第一行包含一个正整数 n,表示数组长度。
第二行包含 n 个正整数 A1,A2,…,An,表示数组 A 中的元素。
输出格式
对于每组数据:输出一行包含一个非负整数,表示最终得分的最大可能值。
样例 #1
样例输入 #1
3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4
样例输出 #1
1
0
8
提示
【样例 1 解释】
对于第一组数据,以下为三种可能的染色方案:
- 将 A1,A2 染成红色,将 A3 染成蓝色(121),其得分计算方式如下:
- 对于 A1,由于其左侧没有红色的数,所以 C1=0。
- 对于 A2,其左侧与其最靠近的红色数为 A1。由于 A1=A2,所以 C2=0。
- 对于 A3,由于其左侧没有蓝色的数,所以 C3=0。
该方案最终得分为 C1+C2+C3=0。
- 将 A1,A2,A3 全部染成红色(121),其得分计算方式如下:
- 对于 A1,由于其左侧没有红色的数,所以 C1=0。
- 对于 A2,其左侧与其最靠近的红色数为 A1。由于 A1=A2,所以 C2=0。
- 对于 A3,其左侧与其最靠近的红色数为 A2。由于 A2=A3,所以 C3=0。
该方案最终得分为 C1+C2+C3=0。
- 将 A1,A3 染成红色,将 A2 染成蓝色(121),其得分计算方式如下:
- 对于 A1,由于其左侧没有红色的数,所以 C1=0。
- 对于 A2,由于其左侧没有蓝色的数,所以 C2=0。
- 对于 A3,其左侧与其最靠近的红色数为 A1。由于 A1=A3,所以 C3=A3=1。
该方案最终得分为 C1+C2+C3=1。
可以证明,没有染色方案使得最终得分大于 1。
对于第二组数据,可以证明,任何染色方案的最终得分都是 0。
对于第三组数据,一种最优的染色方案为将 A1,A2,A4,A5,A7 染为红色,将 A3,A6,A8 染为蓝色(35251214),其对应 C=[0,0,0,5,0,1,2,0],最终得分为 8。
【样例 2】
见选手目录下的 color/color2.in 与 color/color2.ans。
【数据范围】
对于所有测试数据,保证:1≤T≤10,2≤n≤2×105,1≤Ai≤106。
测试点 |
n |
Ai |
1∼4 |
≤15 |
≤15 |
5∼7 |
≤102 |
≤102 |
8∼10 |
≤2000 |
≤2000 |
11,12 |
≤2×104 |
≤106 |
13∼15 |
≤2×105 |
≤10 |
16∼20 |
leq2×105 |
≤106 |