1914 . 彩色紙條
TopCoder
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
5 2
1 2 1 2 1
5 2
1 1 1 2 2
Sample Output 1
2
Sample Input 2
5 3
1 2 3 2 1
5 3
1 2 3 2 3
Sample Output 2
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
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1~2 | 10 |
| 3 | 3 | 20 |
| 4 | 4~7 | 20 |
| 5 | 8~12 | 40 |