algorithm - 寻找最大匹配 Topcoder

Question

这是一道来自 Topcoder SRM 566 Div2 的算法题。

问题可以查看here .

对于那些没有 topcoder 帐户的人，问题描述如下:

Penguin Pals 是一项配对服务，使用以下程序将企鹅与新 friend 配对:

1. 每只企鹅被问到一个问题:“你喜欢蓝色还是红色？”
2. 所有的企鹅都排列成一个圆圈，间距相等。
3. 组织者画了一些直线，连接了几对企鹅。每只企鹅最多只能与另一只企鹅相连。如果两只企鹅喜欢不同的颜色，则不能将它们连接起来。
4. 每只与其他企鹅相连的企鹅都沿着这条线找到他们的匹配项。

上述系统的唯一问题是，如果两条线相互交叉，企鹅就会发生碰撞。因此，采用了新的附加规则:两条线不得交叉。 Penguin Pals 现在有一些企鹅排列成一个圆圈(在上述过程的第 2 步之后)。他们需要知道最多可以创造多少对企鹅。

给你一个字符串 colors ，它的第 i 个字符代表圆形排列中第 i 个企鹅(从 0 开始的索引)的首选颜色。如果第 i 个企鹅喜欢红色，第 i 个字符是“R”，如果第 i 个企鹅喜欢蓝色，则第 i 个字符是“B”。返回可以形成的最大匹配对数。

例子:

“RRBRBRBB”

返回:3

“BBBB”

返回:2

“RRRBRBRBRBRBR”

返回:5

我的方法:

调用长度为n的字符串s。 (注意第0和第n-1个索引是连续的)。

我使用了递归函数 recurse(string s,int i,int j)如下:

int recurse(string s,int i,int j)
{
     if(i>=j)
           return 0;
     if(s[i]==s[j])
        return(1+recurse(s,i+1,j-1));
     else return max(recurse(s,i,j-1),recurse(s,i+1,j));
}

我从 i=0 和 j=n-1 开始，因为如果它们相等，它们将是连续的，用 (i+1,j-1) 调用函数，如果不相等，则调用这两种可能性函数 recurse(s,i,j-1) 和 recurse(s,i+1,j) 并将取这两者中的最大值。

我为每个可能的起始对调用了这个函数，即

用于输入“RRRBRRRBB”。

我用输入调用函数 recurse():

1. s="RRRRRRBB"i=0 j=n-1
2. s="RRBRRBBR"i=0 j=n-1 (将字符串向左移动，之前最左边现在最右边)
3. s="RBRRBBRR"i=0 j=n-1 (同样的操作)

以此类推，直到涵盖所有情况。

但我得到了 WA，但无法确定我的方法中为什么它无法工作的缺陷。

Answer 1

要更正您的解决方案，您应该在每个递归调用中执行以下操作:

s="RRRBRRBB" i=0 j=n-1
s="RRBRRBBR" i=0 j=n-1 (Moved the string left and the earlier leftmost is now the rightmost)
s="RBRRBBRR" i=0 j=n-1 (the same operation)
and so on until all the cases are covered.

但我对这种情况感到 TLE。

解决方案:这是一个简单的问题。

1) 从字符串中删除所有对，其中 s[i] == s[(i+1) % n]，并计算计数。 (i 从 0 到 n-1)。

2) 迭代 #1 直到您的字符串没有转换为“RBRBRBRB...RB”或“BRBRBRBRBR...BR”，对于这种特殊的套管结果(长度/2)- 1；