[ARC002C] コマンド入力
题意翻译
输入指令
高桥君和朋友玩了格斗游戏。
他们玩的游戏的规则是:手柄上有四个键:A、B、X、Y,按照顺序连续按下一定的按键序列,就可以发动连续技。
然而,高桥君平时都不怎么玩格斗类游戏,所以他被朋友吊打了。
手柄上还有两个按键L、R,可以当快捷键使用。L和R都可以代替任意连续的两个按键,加入快捷键就可以让发动连续技的所需按键次数变小。
举个栗子:有一个连续技要求连续按顺序按下:ABXY,这需要按四次;然而,如果设置L=AB,R=XY,这样连续按顺序按下LR就可以发动同样的连续技,这只需要按两次,简化了操作。
高桥君想赢,他想知道一个连续技的指令最少需要按键多少下才能打出。
输入格式:
输入第一行是一个整数N,表示连续技的指令包括N个按键。
第二行是长度为N的字符串,表示连续技的指令。
字符串里每个字符都是A、B、X、Y的其中一个。
输出格式:
输出一个整数,表示添加L、R两个快捷键后,最少按几次可以完成输入的连续技。
注意,最后换行。
感谢@Disconsolate 提供的翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/arc002/tasks/arc002_3
高橋君は友達と格闘ゲームで対戦をすることにしました。
格闘ゲームは $ A $, $ B $, $ X $, $ Y $ の $ 4 $ 種類のボタンを連続で入力するコマンドにより技を繰り出し戦うゲームです。
しかし、普段格闘ゲームで遊ばない高橋君にとってコマンドの入力は難しく、友達に勝てそうにありません。
そこで余っている $ L $ と $ R $ のボタンに連続した $ 2 $ つのボタン入力をショートカットとして割り当てることで、コマンドの入力を短縮したいと思います。
例えば、コマンドが $ ABXY $ だと $ 4 $ 回ボタンを入力する必要がありますが、$ L $ に $ AB $、$ R $ に $ XY $ を割り当てることで $ LR $ の $ 2 $ 回のボタン入力に短縮できます。
$ L $ と $ R $ を用いて入力をなるべく短くした時に必要なボタンの入力回数を求めなさい。 入力は以下の形式で標準入力から与えられる。
> $ N $ $ c_{1}c_{2}...c_{N} $
- $ 1 $ 行目にコマンドに必要なボタンの入力回数を表す $ N $($ 1\ ≦\ N\ ≦\ 1000 $)が与えられる。
- $ 2 $ 行目にコマンドの内容を表す $ N $ 文字の文字列が与えられる。
- $ i $ 文字目の文字である $ c_{i} $ は、`A`, `B`, `X`, `Y` のいずれかで与えられる。
ショートカットを用いてコマンド入力に必要なボタンの入力回数を最小化したときの、ボタン入力回数を標準出力に $ 1 $ 行で出力せよ。
なお、最後には改行を出力せよ。