s02283. CSP-S 2024 复赛 T3 染色

题目描述

时间限制：1s　内存限制：512MB　来源：洛谷 P11233

题目描述

给定一个长度为 $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$ 中所有整数的和，即 $i = 1 \sum n C_{i}$ 。你需要最大化最终得分，请求出最终得分的最大值。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$ ，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含一个正整数 $n$ ，表示数组长度。

第二行包含 $n$ 个正整数 $A_{1}, A_{2}, \dots, A_{n}$ ，表示数组 $A$ 中的元素。

输出格式

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

样例

输入

10
15
4 4 5 5 4 6 4 6 6 4 3 3 4 6 4
15
6 6 6 7 6 6 6 6 4 6 3 4 7 3 6
15
2 8 5 3 1 5 8 3 1 5 2 6 6 8 6
15
1 9 5 1 1 1 9 5 3 2 5 1 5 8 9
15
1 9 6 10 10 7 10 3 5 9 1 3 8 7 4
15
7 1 6 11 11 6 5 5 7 3 6 11 8 1 6
15
2 11 9 6 7 12 12 6 11 12 8 1 10 11 9
15
12 13 7 13 8 13 9 12 1 7 4 9 12 4 12
15
3 14 3 9 3 3 5 14 1 8 4 10 3 14 8
15
15 5 3 15 11 5 15 15 14 10 5 4 8 9 11

输出

说明/提示

【样例 1 解释】

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

将 $A_{1}, A_{2}$ 染成红色，将 $A_{3}$ 染成蓝色（ $121$ ），其得分计算方式如下：

对于 $A_{1}$ ，由于其左侧没有红色的数，所以 $C_{1} = 0$ 。
对于 $A_{2}$ ，其左侧与其最靠近的红色数为 $A_{1}$ 。由于 $A_{1} \neq = A_{2}$ ，所以 $C_{2} = 0$ 。
对于 $A_{3}$ ，由于其左侧没有蓝色的数，所以 $C_{3} = 0$ 。

该方案最终得分为 $C_{1} + C_{2} + C_{3} = 0$ 。

将 $A_{1}, A_{2}, A_{3}$ 全部染成红色（ $121$ ），其得分计算方式如下：

对于 $A_{1}$ ，由于其左侧没有红色的数，所以 $C_{1} = 0$ 。
对于 $A_{2}$ ，其左侧与其最靠近的红色数为 $A_{1}$ 。由于 $A_{1} \neq = A_{2}$ ，所以 $C_{2} = 0$ 。
对于 $A_{3}$ ，其左侧与其最靠近的红色数为 $A_{2}$ 。由于 $A_{2} \neq = A_{3}$ ，所以 $C_{3} = 0$ 。

该方案最终得分为 $C_{1} + C_{2} + C_{3} = 0$ 。

将 $A_{1}, A_{3}$ 染成红色，将 $A_{2}$ 染成蓝色（ $121$ ），其得分计算方式如下：

对于 $A_{1}$ ，由于其左侧没有红色的数，所以 $C_{1} = 0$ 。
对于 $A_{2}$ ，由于其左侧没有蓝色的数，所以 $C_{2} = 0$ 。
对于 $A_{3}$ ，其左侧与其最靠近的红色数为 $A_{1}$ 。由于 $A_{1} = A_{3}$ ，所以 $C_{3} = A_{3} = 1$ 。

该方案最终得分为 $C_{1} + C_{2} + C_{3} = 1$ 。

可以证明，没有染色方案使得最终得分大于 $1$ 。

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

对于第三组数据，一种最优的染色方案为将 $A_{1}, A_{2}, A_{4}, A_{5}, A_{7}$ 染为红色，将 $A_{3}, A_{6}, A_{8}$ 染为蓝色（ $35251214$ ），其对应 $C = [0, 0, 0, 5, 0, 2, 1, 0]$ ，最终得分为 $8$ 。

【样例 2】

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

【数据范围】

对于所有测试数据，保证： $1 \leq T \leq 10$ ， $2 \leq n \leq 2 \times 1 0^{5}$ ， $1 \leq A_{i} \leq 1 0^{6}$ 。

测试点	$n$	$A_{i}$
$1 \sim 4$	$\leq 15$	$\leq 15$
$5 \sim 7$	$\leq 1 0^{2}$	$\leq 1 0^{2}$
$8 \sim 10$	$\leq 2000$	$\leq 2000$
$11, 12$	$\leq 2 \times 1 0^{4}$	$\leq 1 0^{6}$
$13 \sim 15$	$\leq 2 \times 1 0^{5}$	$\leq 10$
$16 \sim 20$	^	$\leq 1 0^{6}$

s02283. CSP-S 2024 复赛 T3 染色 未做

题目描述

题目描述

输入格式

输出格式

样例

说明/提示

s02283. CSP-S 2024 复赛 T3 染色未做