USACO 项链断裂问题的错误答案 [已关闭]

项链断了

您有一条由 N 个红色、白色或蓝色珠子 (3

            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 。

假设您要在某个时候折断项链，将其平直放置，然后从一端收集相同颜色的珠子，直到到达不同颜色的珠子，并对另一端执行相同的操作（这可能不是与之前收集的珠子颜色相同）。

确定项链应该断裂的位置，以便收集最多数量的珠子。

Example

例如，对于图 A 中的项链，可以收集 8 颗珠子，断裂点位于珠子 9 和珠子 10 之间，或者位于珠子 24 和珠子 25 之间。

在一些项链中，包含白色珠子，如上图 B 所示。收集珠子时，遇到的白色珠子可以被处理为红色或蓝色，然后涂上所需的颜色。表示此配置的字符串将包含三个符号 r、b 和 w。

编写一个程序来确定可以从提供的项链中收集的最大珠子数量。

输入格式

第 1 行：N，珠子的数量 第2行：N个字符的字符串，每个字符为r、b或w

29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

输出格式

单行包含可从提供的项链中收集的最大数量的珠子。

11

输出说明

考虑珠子的两个副本（有点像能够绕过两端）。 11 的字符串被标记。

            Two necklace copies joined here

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb| wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

                    ******|*****

                    rrrrrb|bbbbb  <-- assignments

                5xr .....#|#####  6xb

                    5+6 = 11 total

这是我遇到的 USACO 训练问题；我不断得到不正确的答案。 ...请不要告诉我这是愚蠢的；那没有帮助！ ：D

呵呵，我已经准备好了，但我没有费心去编码。无论如何，我的ideas是这个。

首先，您不需要存储所有珠子颜色（采用澳大利亚拼写！），您只需要存储连续有多少个相同颜色的珠子即可。因此对于：

RRBBBWRR

你只需要存储：

2R 3B 1W 2R

需要注意的一件事是，如果结尾珠子和起始珠子颜色相同，则必须考虑到这一点，所以

RRBBBRR

应存储为

4R 3B
or
3B 4R

一样。请注意，这样做的原因不是为了节省内存或其他任何东西，而是为了确保彼此相邻的珠子具有不同的颜色。我们通过组合相同颜色的珠子来做到这一点。

接下来，您将逐一浏览：
- 如果是红色，则将之后的所有值相加，直到找到蓝色，然后继续添加，直到找到另一个红色
- 如果是蓝色，则进行类似操作，但相反
- 如果它是白色的，那么下一个珠子将为红色或蓝色。除添加白色珠子的数量外，按上述操作

这里有些例子。 | 标记序列的开始和结束位置。

B|RB|R

我们找到一个R，然后是一个B，然后是另一个R。因此我们必须在B处停下来。

B|RWRB|R

我们找到了一个 R，然后找到了另一个 R，但我们还没有找到 B，所以我们继续。然后我们找到一个 B，然后又找到一个 R。这一次，既然我们找到了 B，我们就必须停下来。

B|RBW|R

我们找到一个 R，然后找到一个 B，但我们可以继续，因为下一个是 W，然后我们找到另一个 R，所以我们必须停止。在

B|WRBWB|R

我们数W，然后找到R。因此，我们继续直到找到B，然后继续，直到找到另一个R。这

B|WBRWR|B

是一个相反的情况。

现在您所要做的就是实施它：D。当然，这并没有考虑 R、B 和 W 中珠子的实际数量，而只是单个珠子序列的示例。您必须检查所有可能的序列。您还必须处理从后到头的序列。

最后，您可能会注意到这个算法有时很浪费，但 N 一秒钟内。如果有什么令人困惑的地方，请发表评论，因为我不是最好的解释者。快乐编码。