问题 C: 染色（color）

---

【题目描述】

【题目描述】 
给定一个长度为n的正整数数组A，其中所有数从左至右排成一排。 
你需要将A中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分： 
设C为长度为n的整数数组，对于A中的每个数Ai（1≤i≤n）：
•如果Ai左侧没有与其同色的数，则令Ci=0。 
•否则，记其左侧 与其最靠近的同色数 为Aj，若Ai=Aj，则令Ci=Ai，否则令 Ci=0。 
你的最终得分为C中所有整数的和，即 。你需要最大化最终得分，请求出最 终得分的最大值。

【输入】

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

【输出】

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

【提示】

【样例1解释】 
对于第一组数据，以下为三种可能的染色方案： 
1.将A1,A2染成红色，将A3染成蓝色（121），其得分计算方式如下： 
•对于A1，由于其左侧没有红色的数，所以C1=0。 
•对于A2，其左侧与其最靠近的红色数为A1。由于A1=A2，所以C2=0。 
•对于A3，由于其左侧没有蓝色的数，所以C3=0。 
该方案最终得分为C1+C2+C3=0。 
2.将A1,A2,A3全部染成红色（121），其得分计算方式如下： 
•对于A1，由于其左侧没有红色的数，所以C1=0。 
•对于A2，其左侧与其最靠近的红色数为A1。由于A1=A2，所以C2=0。 
•对于A3，其左侧与其最靠近的红色数为A2。由于A2=A3，所以C3=0。 
该方案最终得分为C1+C2+C3=0。 
3.将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 染为蓝色（35152124），其对应C=[0,0,0,5,0,1,2,0]，最终得分为8。


【数据范围】 
对于所有测试数据，保证：1≤T≤10，2≤n≤2×100000，1≤Ai≤1000000。

测试点	n	Ai
1~4	≤15	≤15
5~7	≤100	≤100
8~10	≤2000	≤2000
11、12	≤20000	≤1000000
13~15	≤200000	≤10
16~20	≤200000	≤1000000

题目类型~

CSP-S2024T3 

咻咻~

提交答案 状态 返回作业