TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4256
  • 题目
  • P4256科学馆翻窗
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 1s
    问题描述

    科学馆是个好地方。

    众所周知,某些同学经常忘记带钥匙,因此出入科学馆和科学馆的小机房经常需要翻窗。然而鬼鬼祟祟的行为被其他人看见就不好了。于是,大家打算充分发扬团队协作精神,派几位同学放风。

    为了改进翻窗技巧,你现在弄到了科学馆的监控录像想要进行研究。录像记录下了一些同学翻窗的过程。科学馆的窗户可以用大写字母A~Z表示,那么录像的信息就可以用一个只包含大写英文字母的字符串表示。从左到右的顺序就是时间顺序。每个大写字母表示有一位同学进入了该大写字母表示的窗户里。

    假设你提前你想知道所有同学的翻窗顺序,现在由你安排放风,必须满足下列的条件:放风的同学不会参与翻窗,翻窗的同学也不能参与放风。对于每扇窗户,需要在第一个翻它的同学翻窗前派人放风;可以在最后一个翻它的同学翻过之后不再派人放风。注意,第一个和最后一个同学进入的时刻都需要有人放风。你想知道对于整个过程,最少需要几个放风的同学。

    输入格式

    仅一行,包含一个长度为N且只包含大写英文字母的字符串。

    输出格式

    仅一行,包含一个整数M,表示最少需要几个放风的同学。

    样例输入

    BCBACC

    样例输出

    2

    提示

    【样例解释】

     

    第一个同学翻窗户时,需要派一个人在B窗口处放风。第二个同学翻窗户时,需要派另一个人在C窗口放风。第三个同学翻窗户时,由于之前已经有一个人在B窗口处放风,不需要新安排放风的人;由于他是最后一个翻B窗户的同学,所以在他翻完窗后,原来在B窗口出放风的人可以去A窗口放风。

     

    【数据范围】

    对于30%的数据,N≤20

    对于60%的数据,N≤1000

    对于100%的数据,N≤100000


    来源  OBlack_rgnoH