Subject to the effect: algorithms, compression is useful because the storage and transfer speed, which can speed up and people can see more comfortable ... In this issue, we are so compressed a string: For example, AAAAAAAA can be compressed into 8 (A); AAAAAAAAAABABABCCD can be compressed into 10 (A) 2 (BA), B2 (C) D, can also be compressed into 9 (A) 3 (AB) CCD. Obviously, the back of a compression short, so this is the optimal solution for this problem. Such compression can be nested, that ABABABCDCDCDABABABCDCDCD can be compressed into a 3 (3 (AB) (CD)). Now give you a 100 character within the string, you output the length of the smallest compression, Special Judge.

This title is the most typical interval merger problem. Interval merge the best way of course is DP. Dyna [i] [j] represents the minimum compressed length of the string from i to j in accordance with the general idea of ​​the problem of the interval, there should be DYNA [i] [j] = min (the DYNA [i] [K] + DYNA [k + 1] [j]).

Then we found that simply represents a length, the final output is very troublesome. May wish to set up a structure, which has two fields: a is the content, is a number of repetitions. Established after an interval "packaged" concept: AB, the number of repetitions for 2 field should be packaged into "ABAB" (because of more than 2 (AB) "shorter); repeated 3" 3, (AB) "a, that is to select the shortest way.

But this problem is not a simple addition. "+" Should represent a merger. So the plus sign should have the following meanings:

First, if (i, k) and (k + 1, j), it will repeat number plus 1;

Second, if not identical, the content is packaged after the results of the two intervals is connected to the repeat count is 1.

After select the inside length of the shortest interval as the answer. Another point, if the two values ​​of k such a manner that the length of this interval the same, but the number of repetitions should be selected to repeat comparative a. Because (ABAB, 1) (AB, 2) the length is 4, but the former can not with AB rejoined.

This theme SPJ seems to have a problem, should be able to pay a few AC (the premise is not a big error ...).