← 返回题目列表

AtCoder · joisc2009_chopsticks

chopsticks. 筷子

中文机器翻译题面 查看原题

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

塗り箸 (Chopsticks) - 原题 PDF 第 1 页
原题PDF第3页
可复制的 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