比赛场次	146
比赛名称	20120707
比赛状态	已结束比赛成绩
开始时间	2012-07-07 08:00:00
结束时间	2012-07-07 12:00:00
开放分组	全部用户
注释介绍	2012暑假培训A班

题目名称	表达式游戏
输入输出	`expression.in/out`
时间限制	2000 ms (2 s)
内存限制	128 MiB
测试点数	10 简单对比

用户	结果	时间	内存	得分
zhangchi	AWWWWAAWWW	0.003 s	0.17 MiB	30
fuhao	AWWWWAAWWW	0.003 s	0.17 MiB	30
CC	AWWWWAAWWW	0.003 s	0.31 MiB	30
Citron酱	AWWWWAAWWW	0.004 s	0.31 MiB	30
王者自由	AWWWWAAWWW	0.004 s	0.31 MiB	30
ZhouHang	AWWWWAAWWW	0.004 s	0.31 MiB	30
TBK	AWWWWAAWWW	0.004 s	0.31 MiB	30
Makazeu	AWWWWAAWWW	0.011 s	0.31 MiB	30
kaaala	AWWWWAAWWW	0.012 s	0.32 MiB	30
wo shi 刘畅	WWWWWWAWWW	0.002 s	0.17 MiB	10
Czb。	C	0.000 s	0.00 MiB	0

表达式游戏

★★☆ 输入文件：expression.in 输出文件：expression.out 简单对比
时间限制：2 s 内存限制：128 MiB

【题目描述】

一个字符串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