#P1028. 【USACO题库】1.1.4 Broken Necklace 破碎的项链

【USACO题库】1.1.4 Broken Necklace 破碎的项链

有一条由 n 个红色、白色、或蓝色的珠子组成的项链 (3n35000),珠子顺序完全是随机的。这里是 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 个珠子。

请编程来确定从一条项链上,最多可以被收集的珠子数目。