Responsive image

问题 G: 宝石消除

问题 G: 宝石消除

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 51
[提交][状态][讨论版][命题人:]

题目描述

煜正在玩一个消除游戏。
初始有 n 个宝石从左到右排成一排，第 i 个宝石的颜色为 coli,煜可以进行若干次以下操作：
任选一种颜色 x，将颜色为 x 的最右边那颗宝石、以及该宝石右边的所有宝石全部消除。
煜想知道至少需要几次操作才能把 n 个宝石全部消除。

输入描述

第一行包含一个整数 T (1≤T≤2⋅105)，表示 T 组测试数据。
对于每组测试数据：
第一行包含一个整数 n (1≤n≤2⋅105)，表示初始宝石的数量。
第二行包含 n 个整数 col1,col2,…,coln(1≤coli≤min⁡(n,2))，表示每个宝石的颜色。
保证 ∑n 不超过 2⋅105。

输出描述

对于每组测试数据，输出一个整数，表示把 n 个宝石全部消除所需要的最少操作次数。

样例输入

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

样例输出

2
2
6
1

提示

第一组测试数据：

初始宝石为 [1,2,1]；

第 1 次操作选择颜色 2，可以消除最右边的 2 个宝石，当前剩余宝石为 [1]；

第 2 次操作选择颜色 1，即可把所有宝石都消除。

第三组测试数据：

初始宝石为 [2,2,1,2,2,1,1,2,2,1,2]；

第 1 次操作选择颜色 1，可以消除最右边的 2 个宝石，当前剩余宝石为 [2,2,1,2,2,1,1,2,2]；

第 2 次操作选择颜色 1，可以消除最右边的 3 个宝石，当前剩余宝石为 [2,2,1,2,2,1]；

第 3 次操作选择颜色 2，可以消除最右边的 2 个宝石，当前剩余宝石为 [2,2,1,2]；

第 4 次操作选择颜色 1，可以消除最右边的 2 个宝石，当前剩余宝石为 [2,2]；

第 5 次操作选择颜色 2，可以消除最右边的 1 个宝石，当前剩余宝石为 [2]；

第 6 次操作选择颜色 2，即可把所有宝石都消除。

[提交][状态]
ACM算法攻关部