2-6 Tenzing and Balls

暂无测试数据。

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

F. Tenzing and Balls

Enjoy erasing Tenzing, identified as Accepted!

时间限制:1 seconds

空间限制:256 megabytes

原题链接:https://codeforces.com/gym/451807/problem/F

题目描述

Tenzing有\(n\)个球排成一排。左边第\(i\)个球的颜色是\(a_i\)。

Tenzing可以做任何次数的以下操作:

选择\(i\)和\(j\),使得\(1\leq i<j \leq |a|\)且\(a_i=a_j\),

从数组中删除\(a_i,a_{i+1},\ldots ,a_j\)(并将\(a_j\)右侧所有元素的下标减少\(j-i+1\))。

Tenzing想知道他最多可以取出多少个球。

输入

每个测试包含多个测试用例。第一行输入包含一个整数\(t\)(\(1\leq t\leq 10^3\))--测试案例的数量。测试用例的描述如下。

第一行包含一个整数\(n\)(\(1\leq n\leq 2\cdot 10^5\))--球的数量。

第二行包含\(n\)个整数\(a_1,a_2,\ldots,a_n\)(\(1\leq a_i \leq n\))--球的颜色。

保证所有测试案例的\(n\)之和不超过\(2\cdot 10^5\)。

输出

对于每个测试案例,输出Tenzing能够移除的最大球数。

样例

输入样例

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

输出样例

4
3

样例解释

在第一个例子中,Tenzing将在第一次运算中选择\(i=2\)和\(j=3\),从而得到\(a=[1,3,3]\)。然后Tenzing在第二次操作中又会选择\(i=2\)和\(j=3\),这样就有了\(a=[1]\)。因此,Tenzing总共可以取出\(4\)个球。

在第二个例子中,Tenzing在第一次也是唯一的一次操作中会选择\(i=1\)和\(j=3\),这样\(a=[2]\)。所以Tenzing总共可以取出\(3\)个球。

2023暑假集训7月5日训练题

未参加
状态
已结束
规则
ACM/ICPC
题目
7
开始于
2023-07-05 09:00
结束于
2023-07-05 11:30
持续时间
2.5 小时
主持人
参赛人数
21