Не удается обнаружить случаи тестирования, когда мой код получает неправильный ответ в этой проблеме последовательности скобок

Question

Это проблема для OJ .

Вам дана последовательность S скобок.Вас просят вставить в S как можно меньше скобок, чтобы полученная последовательность T была хорошо согласована.

Можете ли вы сказать, сколько разных T вы можете получить?

Допустим, S = ()), вы можете получить либо (()), либо ()().

Одна строка содержит последовательность S.

• Для 30% данных 1 ≤ |S| ≤ 10.
• Для 60% данных: 1 ≤ |S| ≤ 200.
• Для 100% данных: 1 ≤ |S| ≤ 1000.

Вывести 2 целых числа, указывающих минимальное числоскобок необходимо вставить в S и количество различных T.Число различных T может быть очень большим, поэтому выведите ответ по модулю 10^9+7.

. Способ решения этой проблемы состоит в том, чтобы разбить исходную последовательность на две части.Нужно только вставить (, а другому - только ).Эту буксирную часть можно решить аналогичным образом.

Рассмотрим последовательность (()(().Чтобы избавиться от повторения, мы вставляем ) перед ( или в последнюю позицию последовательности.Количество ), которое можно вставить в каждую позицию, ограничено, пусть оно будет limit[i].

Примите f[i][j] в качестве количества результатов, если j;) вставляются в первую позицию i, затем f[i][j] = f[i-1][0] + f[i-1][1] + ... f[i-1][min(j, limit[i-1])].

Однако, когда я отправил свой код, я получил 60/100 WA.И я не смог проверить случаи, приведшие к моему неправильному ответу, поэтому я не знаю, как улучшить код.

Ниже приведен код, который я отправил:

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

const int modulo = pow(10, 9) + 7;

int split(string);
void inverse(string&);
void getInsLimit(vector<int>&, string, int&);
int getNumOfWays(vector<int>);

int record[1001][1001]; // record nums of ways to insert j parenthesies into the first i position

int main() {

    string input;
    while (getline(cin, input)) {
        int LRpos = split(input); // return the pos after the last ele of L 
        string L = input.substr(0, LRpos), R = input.substr(LRpos, input.size() - LRpos);
        inverse(L);

        int insCnt = 0, wayCnt = 0, tmpL = 0, tmpR = 0;


        vector<int> insLimit;
        getInsLimit(insLimit, L, insCnt);
        tmpL = getNumOfWays(insLimit);


        getInsLimit(insLimit, R, insCnt);
        tmpR = getNumOfWays(insLimit);

        if (tmpL == 0 || tmpR == 0) {
            wayCnt = tmpL + tmpR;
        }
        else {
            for (int i = 0; i < tmpL; ++i) {
                wayCnt += tmpR;
                if (wayCnt >= modulo) {
                    wayCnt -= modulo;
                }
            }

        }

        cout << insCnt << ' ' << wayCnt << endl;

    }

    return 0;
}

int split(string input) {
    int pos = 0;
    int lcnt = 0;
    for (string::size_type i = 0; i < input.size(); ++i) {
        if (input[i] == '(') {
            ++lcnt;
        }else {
            --lcnt;
        }
        if (lcnt < 0) { // less than 0 means it needs '('
            lcnt = 0;
            pos = i + 1;
        }
    }
    return pos;
}

void inverse(string &str) {
    for (string::size_type i = 0; i < str.size(); ++i) {
        str[i] = str[i] == '(' ? ')':'(';
    }
}

void getInsLimit(vector<int>& insLimit, string str, int& insCnt) {
    insLimit.clear();

    if (str.empty())
        return;

    int lCnt = 0;
    for (string::size_type i = 0; i < str.size(); ++i) {
        if (str[i] == '(') {
            ++lCnt;
        }else {
            --lCnt;
        }
        if (lCnt > 0 && (i == str.size() - 1 || str[i + 1] == '(')) {
            insLimit.push_back(lCnt);
        } 
        if (lCnt == 0) { // means that it needn't parenthesies at all
            insLimit.clear();
        }
    }

    insCnt += lCnt;
}

int getNumOfWays(vector<int> insLimit) {

    if (insLimit.empty()) {
        return 0; 
    }

    int maxI = insLimit.size() - 1, maxJ = insLimit[maxI];

    memset(record, 0, 1001 * 1001);

    // Initialize the first line
    for (int j = 0; j <= insLimit[0]; ++j) { // can be equal
        record[0][j] = insLimit[0]; // actually it can only be 1
    }

    for (int i = 1; i <= maxI; ++i) {
        for (int j = 0; j <= insLimit[i]; ++j) { // after limit, record[i][j] = 0, equals initial value
            if (j == 0)
                record[i][j] = 1;
            else {
                record[i][j] = record[i - 1][j] + record[i][j - 1];
                if (record[i][j] >= modulo)
                    record[i][j] -= modulo;
            }
        }
    }

    for (int j = 0; j < maxJ; ++j) {
        record[maxI][j] = 0;
    } // logically should be 0, unnecessary in this problem

    return record[maxI][maxJ];
}