项链断裂问题中的错误答案USACO

Question

断项链

您有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代表红色的珠子，如下所示：brbrrrbbbrrrrrbrrbbrbbbbbrrrrb。

假设您要折断项链，将其笔直摆放，然后从一端收集相同颜色的珠子，直到到达另一种颜色的珠子，然后在另一端进行相同的操作（这可能不是与之前收集的珠子颜色相同）。

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

例

例如，对于图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

Answer 1

嘿，我可以解决这个问题，但是我没有为它编写代码的麻烦。无论如何，我的 想法 是这样。

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

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<350，因此即使O（N^3）也应在1秒钟内起作用。也许是2。无论如何，我相信这是O（N ^2），所以您应该能够 _在一秒钟内_运行该程序350次。如果有什么令人困惑的地方，请发表评论，因为我不是最好的解释者。快乐的编码。