你有一条项链,它由 N 个随机排列的红、白和蓝色的珠子组成(3<=N<=350)。下面的例子展示了两条 N=29 时的项链:
1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figure A Figure B
r red bead
b blue bead
w white bead
项链上的第一个和第二个珠子已经在图中标出了。
图 A 也可以用一个由 b 和 r 组成的字符串直接表示,b 代表蓝色而 r 代表红色,如下所示:brbrrrbbbrrrrrbrrbbrbbbbrrrrb。
假设你想从项链的某处将它截断拉直;接着从一端向另外一端数收集同颜色的珠子,直到碰到一个不同颜色的珠子为止;然后再从另外一端做同样的操作。(一端收集的珠子颜色可以不同于另一端的。)
请想办法找到一个截断项链的位置,能够让我们尽量多地收集到同色的珠子。
例子
如图 A 中的项链,从第 9 和第 10 个或者第 24 和 第 25 个珠子中间截断,则我们可以收集到 8 个珠子。
图 B 中的项链有白色的珠子,当遇到白色的珠子时,它既可以作为蓝色的珠子看待,也可以作为红色的珠子看待,由收集珠子时的需求决定。包含有白色珠子的项链则会由 r、b 和 w 字符组成的字符串来表示。
请编写一个程序计算从某条项链中能够收集到多少个珠子。
输入格式
第一行: N,项链上珠子的个数
第二行:一个字符串,长度为 N,由 r、b 和 w字符组成
输入样例
29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
输出格式
输出一行字符,它应该包含了计算出的结果。
输出样例
11
测试输入
期待的输出
时间限制
内存限制
额外进程
测试用例 1
以文本方式显示
-
29↵
-
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb↵
|
以文本方式显示
|
1秒 |
1024KB |
0 |
废话少说,上程序:
提供几个测试例:
输入:
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
77
rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr
50
bbrrrbrrrrrrrrbrbbbrbrrbrrrrbbbrbrbbbbbrbrrrbbrbbb
17
wwwwwwwwwwwwwwwww
3
rrr
输出:
11
74
9
17
3
分享到:
相关推荐
多年以来,当程序员们推选出最心爱的计算机图书时,《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺,计算机科学大师Jon Bentley以其独有的洞察力和创造力,从磨砺程序员的实际问题中凝结出一篇篇...
编程珠玑 第2版 azw3格式电子书,适合kindle... Dobb's Joumal杂志的特约编辑,他的“编程珠玑”专栏多年来一直是顶级学术杂志Communications of the ACM最风行的特色专栏之一,而本书正是建立在这些专栏的基础之上。
多年以来,当程序员们推选出最心爱的计算机图书时,《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺,计算机科学大师Jon Bentley以其独有的洞察力和创造力,从磨砺程序员的实际问题中凝结出一篇篇...
多年以来,当程序员们推选出最心爱的计算机图书时,《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺,计算机科学大师Jon Bentley以其独有的洞察力和创造力,从磨砺程序员的实际问题中凝结出一篇篇...
多年以来,当程序员们推选出*心爱的计算机图书时,《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺,计算机科学大师Jon Bentley以其独有的洞察力和创造力,从磨砺程序员的实际问题中凝结出一篇篇...
多年以来,当程序员们推选出最心爱的计算机图书时,《编程珠玑》总是位列前列。正如自然界里珍珠出自细沙对牡蛎的磨砺,计算机科学大师Jon Bentley以其独有的洞察力和创造力,从磨砺程序员的实际问题中凝结出一篇篇...
编程珠玑(programming pearls)最早刊登在communications of the ACM 杂志上,有个连载的专栏。文章从1983年到1987年,一共30篇。 目前的书籍编程珠玑>>就是作者在上述文章的基础上修改而成的。 然而,无论你是否...
书中的内容大多出自发表在《Communications of the ACM》上的Programming Pearls专题,它们被整理、修订,并于1986年作为本书第一版出版。本书对第一版十三章中的十二章做了大量的编辑更动,并加入了三个新的主题。
众多大师级程序员强力推崇的书籍,里面的内容大都出自ACM。本书是为程序员所写。
多年以来,当程序员们推选出最心爱的计算机图书时,《编程珠玑》总是位列前列。 正如自然界里珍珠出自细沙对牡蛎的磨砺,计算机科学大师Jon Bentley以其独有的洞察力和创造力, 从磨砺程序员的实际问题中凝结出一篇...
编程珠玑 作者20年前(从1983年到1987年)在communications of the ACM 上连载发表的30篇文章,比《编程珠玑》书写的要详细。很启发人的。
本书的目标读者是准备去硅谷找工作的码农,也适用于在国内找工作的码农,以及刚接触ACM算法竞赛的新手。 市场上讲解算法的书已经汗牛充栋,为什么还要写这本书呢?主要原因是我对目前市场上的大部分算法书都不太满意...