以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

可复制的 PDF 提取文本
Chopsticks: 塗り箸
input ファイル“chopsticks.in”
output 標準出力
ソースファイルchopsticks.c/chopsticks.cpp
時間制限1 秒/ データ
漆塗りお箸協会(Japan Ohashi Institute) は,お箸の国際普及のためにデザインされたお箸
を用意することになった.お箸のうち,彩色される部分は一端から長さNmm にわたる部分で,
1mm ごとに色が定まっており,色が塗られない部分はない.また,お箸の彩色に使用する漆の
色は52 色である.
漆塗り職人のあなたは,決められた色の通りに,お箸を塗る作業を依頼された.漆塗りには
手間がかかるため,なるべく少ない作業回数でお箸を完成させたい.
お箸を塗るための1 作業とは,連続する区間を選び,その区間すべてを一色で塗ることであ
る.この際,すでに色が塗られていた場所も必ず新しい色となる.お箸を完成させるために必
要な作業回数の最小値を求めるプログラムを書け.
Input. 入力ファイルchopsticks.in の1 行目には1 つの整数N (1 ≦N ≦300) が書かれて
いる.これはお箸の彩色される部分の長さがNmm であることを表す.
2 行目には,N 文字からなる英字(A~Z, a~z) の列が与えられる.文字列のi 文字目が端から
(i −1)mm からimm までの色を表す.
Output. 出力は,標準出力に行うこと.作業回数の最小値を表す1 つの整数を出力せよ.
採点基準採点用データのうち,配点の20%分については,N ≦20 を満たし,配点の40%分に
ついては,N ≦120 を満たす.
例1
chopsticks.in 標準出力
6 4
JOIIOI
例2
chopsticks.in 標準出力
15 12
PlovdivBulgaria
塗り箸–1/1