Сколько операций переворачивания всех скобок в подстроке строки скобок необходимо, чтобы строка стала «правильной»?

cs.stackexchange https://cs.stackexchange.com/questions/119847

  •  28-09-2020
  •  | 
  •  

Вопрос

Я называю строку скобок «правильной», если каждая открывающая скобка имеет соответствующую закрывающую скобку где-то после нее, а каждая закрывающая скобка имеет соответствующую открывающую скобку где-то перед ней.Например

(())()((()()))

это правильная строка и

)()()(

это неверная строка.

Операция состоит из взятия непрерывной подпоследовательности входной строки и «переворачивания» каждой скобки в этой подпоследовательности.

Для произвольной строки скобок (четной длины) задача состоит в том, чтобы найти наименьшее количество таких операций, необходимых для ее преобразования в «правильную» строку скобок.

Другой способ взглянуть на эту проблему — иметь строку из +1 и -1 и попытаться найти наименьшее количество операций (умножения каждого числа в интервале на -1), необходимых для того, чтобы каждый префикс этой строки стал неотрицательным. и каждый суффикс неположителен.

Это было полезно?

Решение

DP предложил в комментариях ювальных фильмов действительно работает: мы можем решить проблему в $ \ mathcal {o} (n ^ {2}) $ DP.

Первое обратите внимание, что мы можем предположить, что интервалы не могут перекрывать. Воспользуйтесь любыми двумя перекрывающимися интервалами $ [A, B) $ и $ [c, d) $ . Wlog $ a \ leq c $ . Затем мы можем заменить два интервала с интервалами $ [a, c) $ и $ [\ min (b, d ), \ max (b, d)) $ которые не перекрываются, имеют более короткую общую длину и охватить точно такие же элементы.

Замените открывающиеся скобки с помощью $ 1 $ , закрывающие скобки с $ - 1 $ . Теперь проблема соответствует применению минимального количества операций «Multiply Interval на $ - 1 $ ", такой, что каждый префикс имеет неотрицательную сумму, и сумма по всему массиву ноль.

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

Пусть $ dp [m] [s] [0] $ обозначает минимальное количество интервалов, нам нужно использовать такое, что каждая сумма префикса в первом $ m $ Элементы неотрицательны, сумма первого $ m $ Elements - $ s $ , и у нас нет активного интервала. Точно так же $ dp [m] [s] [1] $ - это то же значение, где у нас есть активный интервал.

Если $ m $ th value - $ 1 $ , для $ 0 \ leq s \ leq m $ Мы устанавливаем

    .
  • $ dp [m] [s] [0]= dp [m-1] [s - 1] [0] $
  • $ dp [m] [s] [1]= dp [m - 1] [s + 1] [1] $

в противном случае мы устанавливаем

    .
  • $ dp [m] [s] [0]= dp [m-1] [s + 1] [0] $
  • $ dp [m] [s] [1]= dp [m - 1] [s - 1] [1] $ .

Затем мы заканчиваем и запускаем интервалы, настройка

    .
  • $ dp [m] [s] [0]=min (dp [m] [s] [0], dp [m] [s] [1]) $
  • $ dp [m] [s] [1]=min (dp [m] [s] [1], dp [m] [s] [0] + 1) $

Базовый чехол - $ dp [0] [0] [0]= 0 $ , $ DP [0 ] [0] [1]= 1 $ .

Есть $ \ mathcal {o} (n ^ {2}) $ Штаты, и мы делаем $ \ mathcal {o} (1) $ Работает для расчета каждого из них, поэтому алгоритм работает в $ \ mathcal {o} (n ^ {2}) $ . DP может быть реализован для использования $ \ mathcal {o} (n) $ память только сохранение значений $ DP $ для текущего $ m $ .

Вот реализация алгоритма C ++. 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string str;
    cin >> str;
    int n = str.size();

    vector<int> dp0 = {0}, dp1 = {1};
    for (int m = 1; m <= n; ++m) {
        vector<int> nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i < m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i > 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i > 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i <= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i <= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout << dp0[0] << '\n';
}
.

Другие советы

Хороший вопрос!

Вот проблема в более популярных терминах.

Сбалансированные круглые скобки

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

Понятно, что сбалансированная строка должна начинаться с "(" и заканчиваться на ")".Он также должен быть одинаковой длины.

Проблема минимальных операций для балансировки струны

Позволять s быть непустой строкой круглых скобок длины n.Единственная операция, которую мы можем выполнить, — это перевернуть каждую скобку в подстроке, то есть заменить каждый «(» на «)» и каждый «)» на «(» для некоторых смежных символов в строке.Проблема в том, как найти наименьшее число операций, которые делают s сбалансированный.

Подход с помощью динамического программирования

Каковы соответствующие подзадачи?Они есть dp[i][j] для 0 <= i < j < n, где dp[i][j] — минимальное количество операций, которые балансируют подстроку между индексом i и индекс j включительно.Желаемое минимальное количество операций, которые балансируют s является dp[0][n-1].

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

базовые случаи dp[i][i+1] равно 0, если подстрока между i и i+1 сбалансирован, т. е. «()».В противном случае это 1.

рекуррентное соотношениеЯ буду использовать Java для определения рекуррентного отношения.

void dp(int i, int j) {
    assert 0 <=i && i + 2 < j && j <= L;

    int min = dp[i + 1][j - 1];
    if (s.charAt(i) == ')' && s.charAt(i + 1) == '(') min++;
    if (s.charAt(j) == '(' && s.charAt(j - 1) == ')') min++;

    for (int k = i + 1; k < j - 1; k+=2) {
        if (a[k] == 1 && a[k + 1] == -1) {
            if (min > dp[i][k] + dp[k + 1][j] - 1) {
                min = dp[i][k] + dp[k + 1][j] - 1;
            }
        } else {
            if (min > dp[i][k] + dp[k + 1][j]) {
                min = dp[i][k] + dp[k + 1][j];
            }
        }
    }

    dp[i][j] = min;
}

Рекуррентное отношение возникает из следующего известного свойства сбалансированных строк.Непустая строка является сбалансированной тогда и только тогда, когда она представляет собой объединение двух сбалансированных строк или «(», за которым следует сбалансированная строка, за которой следует «)».

Обработка перед for цикл, который устанавливает min быть dp[i + 1][j - 1] плюс 0, 1 или 2, происходит из-за того, что "(" за которым следует сбалансированная строка, за которой следует ")" должна быть сбалансированной строкой.

Обработка в. for цикл, который пытается сжаться min к dp[i][k] + dp[k + 1][j] минус 0 или 1 для некоторых k это между i и j, обусловлено тем, что объединение двух сбалансированных строк должно быть сбалансированной строкой.

Временная сложность этого подхода $O(n^3)$.Пространственная сложность $O(n^2)$.

Длина самых «несбалансированных» струн

Наименьшая длина строки, которую невозможно сбалансировать менее чем за 2 операции, равна 4.Например, ")((("

Наименьшая длина строки, которую невозможно сбалансировать менее чем за 3 операции, равна 10.Например, ")(((((())("

Наименьшая длина строки, которую невозможно сбалансировать менее чем за 4 операции, равна 22.Например, ")(())))(((((((((((())(".

Вопрос:Какова наименьшая длина строки, требующей не менее 5 операций?Как я подсчитал, оно должно быть больше 28.Однако моих вычислений недостаточно, чтобы определить реальную стоимость.Как быстро мы сможем вычислить эти наименьшие длины?

Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top