P15206 [SWERC 2018] Dishonest Driver

当你抵达戴高乐机场时，你天真地接受了一位无证司机提供的“有竞争力价格”的搭车前往巴黎。结果是一场灾难：不仅价格极高，而且司机为了让这个价格显得合理，让行程变得比必要长得多。 你注意到了这个骗局，因为你多次经过同一个地方：事实上，你的记忆力非常好，能够清楚地记住你走过的路径，包括那位骗子迫使你绕的每一个圈子。 现在，你在警察局报案投诉这位司机，一位警官要求你讲述你的经历。她甚至要求你提供你所走路径的所有细节。因为你不想再花几个小时做这件事，你决定给出一个压缩版本。 假设你记得你经过了地点 A, B, C, D, A, B, C, D。在这种情况下，你宁愿告诉警官“我走了两遍路径 ABCD”，而不是“我走了路径 ABCDABCD”。由于你的路径重复了相同的地点序列，这将显著缩短你的陈述，而不会遗漏任何细节。 更精确地说，你需要编写一个程序，输入为你经过的地点列表，并返回该路径最短压缩形式的大小。这样的压缩路径可以是以下之一： - 一个你经过的单个地点，称为“原子路径”； - 两个压缩路径的连接； - 一个压缩路径的重复，即 $ (C)^n $，表示你连续走了 $ n $ 次由 $ C $ 描述的路径。 压缩路径的大小定义为其中包含的原子路径的数量。

输入包含两行： - 第一行包含一个整数 $ N $，表示路径的长度。 - 第二行包含路径，描述为一个长度为 $ N $ 的字符串。每个地点由一个字母数字字符描述：可以是数字（从 '0' 到 '9'）、小写字母（从 'a' 到 'z'）或大写字母（从 'A' 到 'Z'）。

输出应包含一行，内容为一个整数，表示最短压缩路径的大小。

#### 样例解释 1 该路径的最短压缩形式是 $ (((a)^3b)^2(c)^2d)^2 $。其中包含的原子路径是 $ a $、$ b $、$ c $ 和 $ d $。因此，其大小为 4。 #### 样例解释 2 该路径的最短压缩形式是 $ (a)^2ba $。其中包含的原子路径是 $ a $、$ b $ 和 $ a $。因此，其大小为 3。 ### 数据范围 $ 0 < N \leq 700 $ 翻译由 DeepSeek 完成