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

Question

关闭。这个问题需要更多 focused .它目前不接受答案。












想改进这个问题？更新问题，使其仅关注一个问题 editing this post .

5年前关闭。




Improve this question




splinter 的项链

你有一条由 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

嘿，我已经完成了这个，但我没有费心去编写它。反正我的想法是这样的。

首先，您不需要存储所有珠子的颜色(去澳大利亚拼写!)，您只需要存储一行中相同颜色的珠子的数量。因此对于:

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