TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

89.6% (69/77)

Submission's AC Ratio

46.3% (113/244)

Description

雷文想要把一張紙條用油彩塗上顏色。這張紙條上面有 N 個格子,依序編號為1到N,一開始都是白色(編號為0),而雷文不喜歡白色,想要用編號為1 到M 的M 種顏色塗紙條,並把其中第i 格塗上某個非白色的顏色ci (編號大於0 而不超過M)。
雷文上色的時候,每次可以一筆畫把連續若干格塗上顏色,並且覆蓋過原先塗在格子上的顏色。舉例來說,如果一個紙條上面有5 格,顏色依序為(1,1,1,2,2),那麼雷文可以一筆畫把第2 格到第4 格塗上顏色3,使紙條顏色變成(1,3,3,3,2)。雷文決定好自己想要把紙條塗上那些顏色之後,想要用最少的次數完成塗色。例如雷文想要把有5 個的紙條塗上(1,2,3,2,1),最少需要三次:先把第1 格到第5 格塗上顏色1,再把第2 格到第4 格塗上顏色2,最後把第3 格塗上顏色3。過程如下:
(0,0,0,0,0) → (1,1,1,1,1) → (1,2,2,2,1) → (1,2,3,2,1)
這是最少次數的塗法。請幫他撰寫一個程式,依據雷文的喜好,算出最少要塗幾次才能夠完成。

Input Format

輸入包含多筆測試案例。整個測試資料的第一行有一個整數T,代表總共有T 個測試案例。每個測試案例有兩行,第一行是紙條上的格子數N 以及顏色數M,由空白隔開。第二行有N 個正整數c1, c2, … ,cN,由空白隔開。

Output Format

針對每個測試案例,以一行輸出最少的塗色次數。

Sample Input

輸入範例1:(第一組、第三組)
2
5 2
1 2 1 2 1
5 2
1 1 1 2 2

輸入範例2:(第二組、第四組、第五組)
2
5 3
1 2 3 2 1
5 3
1 2 3 2 3

Sample Output

輸出範例1:
3
2

輸出範例2:
3
4

Hints

本題共有五組測試資料。每組可有多個輸入檔案,全部答對該組才得分。
第一組10分,T ≤ 20、N ≤ 10、M = 2、對所有1 ≤ i ≤ N,ci 均為1或2。
第二組10分,T ≤ 20、N ≤ 10、M ≤ 10、對所有1 ≤ i ≤ N,ci 介於1到M之間。
第三組20分,T ≤ 20、N ≤ 50、M = 2、對所有1 ≤ i ≤ N,ci 均為1或2。
第四組20分,T ≤ 20、N ≤ 50、M ≤ 50、對所有1 ≤ i ≤ N,ci介於1到M之間。
第五組40分,T ≤ 20、N ≤ 200、M ≤ 200、對所有1 ≤ i ≤ N,ci介於1到M之間。

Problem Source

104學年度高級中學資訊學科能力競賽決賽程式設計試題第四題
Set by Paupière

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 7, Score: 20
For Testdata: 8 ~ 12, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 262144
1 1000 131072 262144
2 1000 131072 262144
3 1000 131072 262144
4 1000 131072 262144
5 1000 131072 262144
6 1000 131072 262144
7 1000 131072 262144
8 1000 131072 262144
9 1000 131072 262144
10 1000 131072 262144
11 1000 131072 262144
12 1000 131072 262144