回分類題庫
e028: 4.彩色紙條
關鍵字: 104學年度全國決賽

測資點 : 6 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 23 Times / 17 Users | Submit : 172 Times / 36 Users | Accepted rate : 47%
題目加入時間 : 2016-11-17 13:46

Content: 简体中文

雷文想要把一張紙條用油彩塗上顏色。這張紙條上面有 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:

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

Output:

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

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4
5 2
1 2 1 2 1
5 2
1 1 1 2 2
5 3
1 2 3 2 1
5 3
1 2 3 2 3

Sample Output :

3
2
3
4

Hint :

Author :

104學年度全國決賽 (管理員:sagit)

  Solve it!   Status Forum