雷文想要把一張紙條用油彩塗上顏色。這張紙條上面有 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)
這是最少次數的塗法。
請幫他撰寫一個程式,依據雷文的喜好,算出最少要塗幾次才能夠完成。
輸入包含多筆測試案例。
整個測試資料的第一行有一個整數 T,代表總共有 T 個測試案例。
每個測試案例有兩行,第一行是紙條上的格子數 N 以及顏色數 M,由空白隔開。
第二行有 N 個正整數 c1, c2, ... ,cN,由空白隔開。
針對每個測試案例,以一行輸出最少的塗色次數。
輸入範例 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
輸出範例 1: 3 2 輸出範例 2: 3 4
本題共有五組測試資料。每組可有多個輸入檔案, 全部答對該組才得分。
第一組 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 之間。