【NOIP模拟赛】秘密文件

2014年7月10日1,5790

【问题描述】

某天,情报局得到了一份秘密文件。文件的内容是加密后的全部由大写字母组成字符串。情报局局长小明想将其发送给远在东方神秘的xx大陆上的老朋友小刘来解密。然而若字符串太长,则需要很长的发送时间,太不安全了,因此小明想尽量将其缩短。于是小明制定了这样一个缩短规则:若一个字符串t连续出现k次,则可以用k(t)进行说明。如ABABAB可以缩成3(AB)。当然,重复缩短是允许的,如ABABABAAAAAAARABABAAAAAA可以缩成2(3(AB)6(A))

现在,小明想知道,对于给定的字符串,最短可以缩成什么样子。

【输入格式】

输入仅一行,为给定的字符串。

【输出格式】

输出仅一行,为经过缩短操作后的字符串。

若有多解,输出任意解即可。

【样例输入】

AAAAAAAAAARABABCCD

【样例输出】

9(A)3(AB)CCD

【数据范围】

对于l00%的数据,字符串的长度L≤100。

题解

此题是scoi字符串折叠加强版。。。

输出的是方案

我们只要定义一个string ans[i][j]存下i到j最优解的字符串就行了

合并啥的都很简单。。。