这是来自 Topcoder SRM 566 Div2 的算法问题。
问题可以在这里查看。
对于那些没有 topcoder 帐户的人,问题描述如下:
Penguin Pals 是一项配对服务,可使用以下程序将企鹅与新朋友配对:
- 每只企鹅都被问到一个问题:“你喜欢蓝色还是红色?”
- 所有的企鹅都排列成一个圆圈,它们间隔相等。
- 组织者画了一些直线,连接了几对企鹅。每只企鹅最多只能与另一只企鹅相连。如果两只企鹅喜欢不同的颜色,它们就无法连接起来。
- 每只与其他企鹅相连的企鹅都会沿着这条线找到他们的匹配项。
上述系统的唯一问题是,如果两条线相互交叉,企鹅就会发生碰撞。因此,通过了一条新的附加规则:两条线不得交叉。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() :
- s="RRRBRRBB" i=0 j=n-1
- s="RRBRRBBR" i=0 j=n-1 (将字符串向左移动,之前的最左边现在是最右边)
- s="RBRRBBRR" i=0 j=n-1 (同样的操作)
以此类推,直到涵盖所有案例。
但是我得到了 WA,并且无法确定我的方法中的缺陷为什么它不能工作。