chopsticks - 塗り箸 (Chopsticks) Editorial /

Time Limit: 1 sec / Memory Limit: 64 MiB

AtCoder での提出方法

標準入力から入力を読み込み,標準出力へ出力すること.

配点 : 100 点

問題文

漆塗りお箸協会 (Japan Ohashi Institute) は,お箸の国際普及のためにデザインされたお箸を用意することになった.お箸のうち,彩色される部分は一端から長さ N\:\textrm{mm} にわたる部分で,1\:\textrm{mm} ごとに色が定まっており,色が塗られない部分はない.また,お箸の彩色に使用する漆の色は 52 色である.

漆塗り職人のあなたは,決められた色の通りに,お箸を塗る作業を依頼された.漆塗りには手間がかかるため,なるべく少ない作業回数でお箸を完成させたい.

お箸を塗るための 1 作業とは,連続する区間を選び,その区間すべてを一色で塗ることである.この際,すでに色が塗られていた場所も必ず新しい色となる.お箸を完成させるために必要な作業回数の最小値を求めるプログラムを書け.

入力

入力ファイル chopsticks.in の 1 行目には 1 つの整数 N (1 \leqq N \leqq 300) が書かれている.これはお箸の彩色される部分の長さが N\:\textrm{mm} であることを表す.

2 行目には,N 文字からなる英字 (A~Z, a~z) の列が与えられる.文字列の i 文字目が端から (i - 1)\:\textrm{mm} から i\:\textrm{mm} までの色を表す.

出力

出力は,標準出力に行うこと.作業回数の最小値を表す 1 つの整数を出力せよ.

採点基準

採点用データのうち,配点の 20\% 分については,N \leqq 20 を満たし,配点の 40\% 分については,N \leqq 120 を満たす.

入力例 1

6
JOIIOI

出力例 1

4

入力例 2

15
PlovdivBulgaria

出力例 2

12

Source Name

JOI 2008-2009 春季トレーニング合宿 Contest Day4