Задача на комбинаторику. Нужен код или алгоритм. Также у меня есть свой алгоритм, но не работает.

Question

Задача на комбинаторику. Нужен код или алгоритм. Также у меня есть свой алгоритм, но не работает.

Кирилл Стрикель Профи (756), на голосовании 3 месяца назад

Посчитайте количество правильных скобочных последовательностей длины 2n
(n открывающихся скобок и n закрывающихся), составленных из круглых и квадратных скобок так, что внутри любой пары круглых скобок нет квадратных скобок.
Моя идея.
Для начала сделаем массив дп1, где дп1[i] - это кол-во последовательностей длинной 2 * i
(i открывающихся скобок и i закрывающихся) => это высчитывается по формула(С из 2 * i по i и поделить это на i + 1)
Далее делаем массив дп2, где дп2[i] - ответ на задачу для длинны последовательности 2 * i
(i открывающихся скобок и i закрывающихся). Массив дп2 пересчитываю следующим образом
дп2[i] = дп2[i - 1] + дп[i - 1] --- (я как бы обворачиваю все последовательности в квадратные скобки), ответ всегда получается меньше, чем надо, например для n = 5, ответ равен 625.
Скажите, что не так в моей идеи(или опровергните совсем).
Если у вас есть свои идеи (код тоже принимается=)), то скажите.

Дополнен 4 месяца назад

n до 1000

Answer 1

 #include  
#include  
 
using namespace std; 
 
const int MOD = 1e9 + 7; 
 
vector calculateCatalan(int n) { 
    vector catalan(n + 1, 0); 
    catalan[0] = catalan[1] = 1; 
 
    for (int i = 2; i <= n; i++) { 
        for (int j = 0; j < i; j++) { 
            catalan[i] = (catalan[i] + catalan[j] * catalan[i - 1 - j]) % MOD; 
        } 
    } 
 
    return catalan; 
} 
 
long long countBracketSequences(int n) { 
    vector catalan = calculateCatalan(n); 
    vector dp(n + 1, 0); 
    dp[0] = dp[1] = 1; 
 
    for (int i = 2; i <= n; i++) { 
        dp[i] = dp[i - 1];  // Случай с внешними квадратными скобками 
        for (int j = 0; j < i; j++) { 
            dp[i] = (dp[i] + catalan[j] * dp[i - 1 - j]) % MOD; 
        } 
    } 
 
    return dp[n]; 
} 
 
int main() { 
    int n; 
    cin >> n; 
    cout << countBracketSequences(n) << endl; 
    return 0; 
}

Answer 2

Jurijus Zaksas Искусственный Интеллект (445791) 4 месяца назад

Твой алгоритм не учитывает неправильные последовательности, например )( или [(])
И почему только +-1? А если там 10 скобок сразу открывается?
Думай исчо, юный падаван. Рекомендую использовать стек, раз уж у тебя скобки разные.

Кирилл СтрикельПрофи (756) 4 месяца назад

То есть? Первый вариант точно учитывает, т.к. там правильная формула. а второго варианта точно не может быть, т.к. я всегда обворачиваю дев, четыре, шесть... скобок

Jurijus Zaksas Искусственный Интеллект (445791) Здесь не помогут никакие формулы. Поможет перебор последовательностей и проверка соответствия открытых и закрытых скобок. Ничего "оборачивать" и как-либо модифицировать исходную последовательность не нужно.

Кирилл СтрикельПрофи (756) 4 месяца назад

да

Answer 3

не количество правильных пар, а при обнаружении косяка выдать,что пары в принципе не работают из=за вложенности в ( ) из -за [ ]