表达式游戏

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

【题目描述】

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

然后现在给你一个只有变量和操作符组成的后缀表达式T，请你将它重新排列成一个新的后缀表达式T'，使得T与T'等价，而且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-size为7，而且原输入表达式是等价的。

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

【数据规模】

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

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

【时限】

2s