寻找最大匹配Topcoder

这是Topcoder SRM 566 Div2的一个算法问题。寻找最大匹配Topcoder

问题可以查看here。

对于那些没有TopCoder公司账户的问题说明如下：

企鹅好朋友是匹配企鹅新朋友，使用以下步骤一个媒人服务：

每个企鹅被问单个问题：“你喜欢蓝色还是红色？”
所有的企鹅排列成一个圆形，等距。
组织者绘制一些直线，连接一些企鹅对。每只企鹅最多只能连接一只企鹅。如果他们喜欢不同的颜色，两只企鹅不能连接。
与其他企鹅相连的每只企鹅都会沿着线找到他们的匹配。

上述系统唯一的问题是它允许企鹅碰撞，如果两条线相互交叉。因此，通过了一条新的附加规则：不会有两条线可能交叉。现在企鹅派对上有一些企鹅排成一圈（在上述步骤2之后）。他们需要知道他们可以创造的最大数量的企鹅。

给出一个字符串颜色，其第i个字符表示圆形排列中第i条企鹅（基于0的指数）的首选颜色。如果第i只企鹅更喜欢红色，则第i个字符为'R'，如果第i只企鹅更喜欢蓝色，则第i个字符为'B'。返回可以形成的匹配对的最大数量。

实施例：

“RRBRBRBB”

返回：3

“BBBBB”

返回：2

“RRRBRBRBRBRB”

返回：5

我的方法：

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

我用一个递归函数递归（字符串s，INT I，诠释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）和递归（s，i + 1），j），并将采取这两个最大值。

我称这个功能为每一个可能的开始对即

用于输入“RRRBRRBB”。

我调用的函数递归（）的输入：

S = “RRRBRRBB的” i = 0 J = n-1个
S = “RRBRRBBR的” i = 0 J = N-1（移动离开串和现在较早最左边的是最右边的）
S =“RBRRBBRR的” i = 0 J = n-1个（相同的操作）

，以此类推，直到所有的情况都包括在内。

但是我得到了WA，无法找到我的方法中的缺陷，为什么它无法正常工作。

来源

2013-01-15 Akashdeep Saluja

您的解决方案未能成为以下测试用例RRBB –

@Толя如何失败，我的解决方案返回2，我认为答案也是2.此外，我不怀疑系统裁判我知道我的解决方案不正确，但无法解决找出一个逻辑缺陷。这就是我在这里。 –

您的解决方案返回1.第一次分支后，解决方案搜索答案RRB和RBB的答案1和最大值都为1，结果为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]的字符串中删除所有对，并计算count。（我从0到n-1）。 2）迭代＃1直到你的字符串没有转换为“RBRBRBRB ... RB”或“BRBRBRBRBR ... BR”，这个特殊的套管结果（长度/ 2） - 1;

来源

2013-01-15 13:43:35

可能值得一提的是，预期解决方案记录在Problem Set Analysis page for SRM566上。

来源

2013-02-23 16:59:14 m01

寻找最大匹配Topcoder

回答

相关问题