Блог

Это проблема на 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] , что количество результатов if 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(stringamp;);
void getInsLimit(vector<int>amp;, string, intamp;);
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 amp;str) {
    for (string::size_type i = 0; i < str.size();   i) {
        str[i] = str[i] == '(' ? ')':'(';
    }
}

void getInsLimit(vector<int>amp; insLimit, string str, intamp; 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 amp;amp; (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];
}