1

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

问题可以在这里查看。

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

Penguin Pals 是一项配对服务,可使用以下程序将企鹅与新朋友配对:

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

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

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

例子:

“RRBRBRBB”

回报:3

“BBBB”

回报:2

“RRRBRBRBRBRB”

回报: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) 调用函数,如果不是,则同时调用函数递归(s,i,j-1) 和 recurse(s,i+1,j) 并将取这两者中的最大值。

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

对于输入“RRRBRRBB”。

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

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

以此类推,直到涵盖所有案例。

但是我得到了 WA,并且无法确定我的方法中的缺陷为什么它不能工作。

4

2 回答 2

3

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

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] 的字符串中删除所有对,并计算计数。(我从 0 到 n-1)。

2)迭代#1直到你的字符串没有转换为“RBRBRBRB...RB”或“BRBRBRBRBR...BR”,对于这个特殊的大小写结果(长度/ 2) - 1;

于 2013-01-15T13:43:35.707 回答
1

值得一提的是,预期的解决方案记录在SRM566 的问题集分析页面上

于 2013-02-23T16:59:14.803 回答