P2470 [SCOI2007] Compression

Given a string consisting of lowercase letters, we can compress its repeated information using a simple method. The compressed string may (but does not have to) contain uppercase letters $\texttt{R}$ and $\texttt{M}$ in addition to lowercase letters, where $\texttt{M}$ marks the start of a repeated segment, and $\texttt{R}$ repeats the decompressed result starting from the previous $\texttt{M}$ (if there is no $\texttt{M}$ to the left of the current position, start from the beginning of the string), which is called the buffer string. $\texttt{bcdcdcdcd}$ can be compressed as $\texttt{bMcdRR}$. The decompression process is shown below: Already decompressed part|Decompression result|Buffer string :-:|:-:|:-: $\texttt{b}$|$\texttt{b}$|$\texttt{b}$ $\texttt{bM}$|$\texttt{b}$|$\texttt{.}$ $\texttt{bMc}$|$\texttt{bc}$|$\texttt{c}$ $\texttt{bMcd}$|$\texttt{bcd}$|$\texttt{cd}$ $\texttt{bMcdR}$|$\texttt{bcdcd}$|$\texttt{cdcd}$ $\texttt{bMcdRR}$|$\texttt{bcdcdcdcd}$|$\texttt{cdcdcdcd}$

The input contains a single line with the string to compress, consisting only of lowercase letters, of length $n$.

Output a single line: the minimum possible length of the compressed string.

In the first example, an answer is $\texttt{aaaRa}$. In the second example, an answer is $\texttt{bMcdRRxMcdRR}$. Constraints - For $50\%$ of the testdata, $1\le n \le 20$. - For $100\%$ of the testdata, $1\le n \le 50$. Translated by ChatGPT 5