表达式游戏

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 expression.in 输出文件 expression.out

【题目描述】

一个字符串SRLE-size定义为:将S分为最少的段数k,使得每段里的字符都相同,则k即为SRLE-size。比如“aabbaa”的RLE-size3"aabab"RLE-size4

然后现在给你一个只有变量和操作符组成的后缀表达式T,请你将它重新排列成一个新的后缀表达式T',使得TT'等价,而且T'RLE-size最小。

注意所有的操作符都满足交换律和结合律,而且所有的变量都为小写字母,所有的操作符都为'+', '*', '#', '!', '@', '$', '%' '^'中一个。保证所有表达式合法。

【输入格式】

一行字符串,表示后缀表达式T

【输出格式】

一行一个整数,表示T'的最小RLE-size

【样例输入1

af+b*cd**

【样例输出1

7

【样例输入2

xy*x*y*x*y*

【样例输出2

3

【样例解释】

对于样例1,原输入表达式可重新排列为daf+bc***,其RLE-size7,而且原输入表达式是等价的。

对于样例2,原输入表达式可重新排列为xxxyyy*****或者yyyxxx*****

【数据规模】

对于20%的数据,T的长度不超过10

对于100%的数据,T的长度不超过2500

【时限】

2s