煜正在玩一个消除游戏。
初始有 n 个宝石从左到右排成一排，第 i 个宝石的颜色为 coli,煜可以进行若干次以下操作：
任选一种颜色 x，将颜色为 x 的最右边那颗宝石、以及该宝石右边的所有宝石全部消除。
煜想知道至少需要几次操作才能把 n 个宝石全部消除。
问题 G: 宝石消除
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 51
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行包含一个整数 T (1≤T≤2⋅105)，表示 T 组测试数据。
对于每组测试数据：
第一行包含一个整数 n (1≤n≤2⋅105)，表示初始宝石的数量。
第二行包含 n 个整数 col1,col2,…,coln(1≤coli≤min(n,2))，表示每个宝石的颜色。
保证 ∑n 不超过 2⋅105。
对于每组测试数据：
第一行包含一个整数 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，即可把所有宝石都消除。
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版