破碎的项链
成绩 | 100 | 开启时间 | 2020年02月18日 星期二 11:30 |
折扣 | 0.8 | 折扣时间 | 2020年02月18日 星期二 11:30 |
允许迟交 | 是 | 关闭时间 | 2020年02月18日 星期二 11:30 |
输入文件 | beads.in | 输出文件 | beads.out |
【题目描述】破碎的项链(beads)
有一条由n个由红、白、蓝色的珠子组成的项链,珠子是随意安排的。图3.2是n=29的两个例子,其中第1和第2个珠子已经被标记,A例中的项链可以用字符串“brbrrrbbbrrrrrbrrbbrbbbbrrrrb”表示,r,b,w分别表示红珠子,蓝珠子和白珠子。
图3.2
假如在某处打破项链,展开成一条直线,然后从一端开始收集同颜色的珠子直到遇到一个不同的颜色珠子,在另一端做同样的事(颜色可能与在这之前收集的不同)。 确定应该在哪里打破项链来收集到最大数目的珠子。
例如,在A例中的项链中,在珠子9和珠子10或珠子24和珠子25之间打断项链可以收集到8个珠子。
当收集珠子的时候,一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。
写一个程序来确定从一条被给出的项链可以收集到的珠子最大数目。
【输入格式】
第一行一个正整数n(3≤n≤350),表示珠子数目。
第二行为一串长度为n的字符串,每个字符是r,b或 w。
【输出格式】
输出一个整数,表示从给出的项链中可以收集到的珠子的最大数量。
【输入样例】
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
【输出样例】
11