c481: pD 彩色紙條
標籤 :
通過比率 : 57% (4 人 / 7 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-03-15 12:45

內容

雷文想要把一張紙條用油彩塗上顏色。這張紙條上面有 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
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (8%): 1.0s , <1M
公開 測資點#9 (8%): 1.0s , <1M
公開 測資點#10 (8%): 1.0s , <1M
公開 測資點#11 (8%): 1.0s , <1M
公開 測資點#12 (8%): 1.0s , <1M
提示 :

本題共有五組測試資料。每組可有多個輸入檔案, 全部答對該組才得分。
第一組 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 之間。

標籤:
出處:
104學年度全國資訊學科能力競賽 [編輯:
andy89923 (CTFang)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」