#P1028. 【USACO题库】1.1.4 Broken Necklace 破碎的项链
【USACO题库】1.1.4 Broken Necklace 破碎的项链
有一条由 n 个红色、白色、或蓝色的珠子组成的项链 (3≤n≤35000),珠子顺序完全是随机的。这里是 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
图 A 图 B
r 红珠子
b 蓝珠子
w 白珠子
第一和第二个珠子在图片中已经做好标记。图 A 中的项链可以用这个字符串表示:brbrrrbbbrrrrrbrrbbrbbbbrrrrb
。
假如你要在某些地方切断项链,展开成一条直线,然后从一端开始收集同颜色的珠子直到你遇到一个不同颜色的珠子;在另一端做同样的事(不要求两个端点的颜色相同)。
当收集珠子的时候,一颗白珠子可以被当做红色也可以被当做蓝色,因为后续我们可以对它们染色。
请你确定应该在哪里切断项链,使得你能遵照上述规则收集到最多的珠子。每颗珠子只能被收集一次。举例来说,图 A 中的项链,在珠子 9~10 或珠子 24~25 之间切断项链,可以收集到 8 个珠子。
请编程来确定从一条项链上,最多可以被收集的珠子数目。