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

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

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

RRBBBWRR

您只需要存储：

2R 3B 1W 2R

要注意的一件事是，如果末尾珠和起始珠子的颜色相同，则必须考虑这一点，因此

RRBBBRR

应该存储为

4R 3Bor3B 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次。如果有什么令人困惑的地方，请发表评论，因为我不是最好的解释者。快乐的编码。