0

实际上我正在尝试解决 SPOJ 问题：[SPOJ] http://www.spoj.com/problems/SQRBR/ 。我想出了递归来解决它，但我不知道如何做记忆。任何关于如何记忆给定问题的建议都会有所帮助。我的代码给出了正确的答案，但它在 spoj 中给出了 TLE 这是我的代码：

#include <iostream>
#include <cstdio>

using namespace std;

void balancedParen(int n, int open, int position, int close, char str[], string s,    long long int &counter) {
if(close == n) {
    str[pos] = '\0';
    printf("%s\n", str);
    counter++;
    return;
}

if(s[position] == '(' ) {
  if(open <= n-1) {
    str[position] = '(';
    balancedParen(n, open+1, position+1, close, str, s, counter);
  }
} else {
  if(open < n) {
    str[position] = '(';
    balancedParen(n, open+1, position+1, close, str, s, counter);
  }
  if(open > close) {
    str[position] = ')';
    balancedParen(n, open, position+1, close+1, str, s, counter);
  }
}
    return ;
}

int main() {
      int a[100], n, k, i;
      long long counter = 0;
      int testCases;

      scanf("%d", &testCases);

      while(testCases--) {
              scanf("%d", &n);
              scanf("%d", &k);
              char str[100];
              string s = "..........................................................................";
      for(i = 0; i < k; i++) {
              scanf("%d", &a[i]);
              s[a[i]-1] = '(';
       }
      balancedParen(n, 0, 0, 0, str, s, counter);
      printf("%lld\n", counter);
      counter = 0;
   }
     return 0;
}
4

1 回答 1

0

我可以想到一种相对简单且可能意义重大的优化。

首先，不要将“计数器”作为引用，而是将其作为函数的返回值。在这里听我说一说。

现在说给你的位置是“1、7、15”。而不是递归地去“1、2、3、4、5、6、7”，你可以有点棘手，一步到7。

您只需要计算可用于 1 到 7 之间的排列数，对于每个可能的左括号数（在本例中为 3、4、5 和 6）

例如，有多少种方法可以在 1 和 7 之间有 3 个左括号？

[[[]]]
[[][]]
[][][]
[[]][]
[][[]]

5 个排列（除非我错过了一个）。因此，您可以添加5*balancedParen(n, open+3, position+6, close+3, str, s, counter)到结果中。并对 4、5 和 6 个左括号执行类似的操作。

当然，您需要编写另一个函数（递归方法似乎最简单）才能找到该数字“5”。但好处是函数调用的总数是现在(calls to get from 1 to 7) + (calls to get from 7 to 15)，而不是(calls to get from 1 to 7) * (calls to get from 7 to 15)。

这是一些应该使用我描述的算法工作的代码：

int countPermutations(int unclosed, int length, int toOpen)
{
    if (toOpen > length) // impossible to open this many, not enough length
        return 0;
    int toClose = length-toOpen;
    if (toClose - toOpen > unclosed)
        return 0; // No possibilities; not enough open parens to fill the length
    if (toOpen == 0 || toOpen == length)
        return 1; // Only one possibility now
    int ret = 0;
    if (toOpen > 0) // Count permutations if we opened a paren here
        ret += countPermutations(unclosed+1, length-1, toOpen-1); 
    if (unclosed > 0) // Count permutations if we closed a paren here
        ret += countPermutations(unclosed-1, length-1, toOpen); 
    return ret;
}

int countNLengthSolutions(int n, int unclosed, int position, int *positions, int remainingPositions)
{
    if (n % 2 != 0)
        return 0; // must be a length divisible by 2
    if (position > n)
        return 0;
    if (n-position < unclosed)
        return 0; // too many open parens, no way to complete within length

    if (remainingPositions == 0)
    {
        // Too many open parens to close by the time we get to length N?
        if ((n - position) < unclosed) 
            return 0;
        else // Say we have 4 open and a length of 10 to fill; we want (10-4)/2 = 3 more open parens.
            return countPermutations(unclosed, n-position, (n-position - unclosed)/2); 
    }
    else
    {
        int ret = 0;
        int toFill = *positions - position - 1;
        for (int openParens = 0; openParens <= toFill; openParens++)
        {
            int permutations = countPermutations(unclosed, toFill, openParens);
            if (permutations > 0)
                ret += permutations*countNLengthSolutions(n, unclosed+(2*openParens-toFill)+1, position+toFill+1, positions+1, remainingPositions-1);
        }
        return ret;
    }
}

我可能在某处有错误，我并没有真正花时间检查，但我验证它适用于所有示例输入。

于 2013-05-22T20:52:36.050 回答