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:
Output:
Sample Input:
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
: