题库 信息学奥赛题库 题目列表 染色(color)【题目描述】给定一个长度为 n ...
问答题

染色(color)

【题目描述】

给定一个长度为 的正整数数组 A,其中所有数从左至右排成一排。 你需要将 中的每个数染成红色或蓝色之一,然后按如下方式计算最终得分: 设 为长度为 的整数数组,对于 中的每个数 Ai(≤ ≤ n):

• 如果 A左侧没有与其同色的数,则令 C= 0。 否则,记其左侧.........Aj,若A=Aj,则令C=Ai,否则令C= 0

你的最终得分为 中所有整数的和,即你需要最大化最终得分,请求出最即终得分的最大值。

【输入格式】

从文件 color.in 中读入数据。

....
输入的第一行包含一个正整数 T,表示数据组数。
接下来包含 
组数据,每组数据的格式如下: 第一行包含一个正整数 n,表示数组长度。
第二行包含 
个正整数 A1, A2, . . . , An,表示数组 中的元素。

【输出格式】

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

【样例 输入】

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

【样例 1 输出】



8

【样例 解释】

对于第一组数据,以下为三种可能的染色方案:
1. 将 A1, A染成红色,将 A染成蓝色(121),其得分计算方式如下:

  • 对于 A1,由于其左侧没有红色的数,所以 C= 0

  • 对于 A2,其左侧与其最靠近的红色数为 A1。由于 A̸A2,所以 C= 0

  • 对于 A3,由于其左侧没有蓝色的数,所以 C= 0

    该方案最终得分为C+C+C= 0

2. 将 A1, A2, A全部染成红色(121),其得分计算方式如下:

  • 对于 A1,由于其左侧没有红色的数,所以 C= 0

  • 对于 A2,其左侧与其最靠近的红色数为 A1。由于 A̸A2,所以 C= 0

  • 对于 A3,其左侧与其最靠近的红色数为 A2。由于 A̸A3,所以 C= 0

    该方案最终得分为C+C+C= 0

3. 将 A1, A染成红色,将 A染成蓝色(121),其得分计算方式如下:

  • 对于 A1,由于其左侧没有红色的数,所以 C= 0

  • 对于 A2,由于其左侧没有蓝色的数,所以 C= 0

  • 对于 A3,其左侧与其最靠近的红色数为 A1。由于 AA3,所以 CA= 1

    该方案最终得分为C+C+C= 1。 可以证明,没有染色方案使得最终得分大于 1。 对于第二组数据,可以证明,任何染色方案的最终得分都是 0。 对于第三组数据,一种最优的染色方案为将 A1, A2, A4, A5, A染为红色,将 A3, A6, A8

    染为蓝色(35152124),其对应 = [00050120],最终得分为 8。 

【样例 2

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

【数据范围】

对于所有测试数据,保证:≤ ≤ 10≤ ≤ 2×105≤ A≤ 106

题目信息
完善程序 2024年 复赛
-
正确率
0
评论
58
点击