Quante operazioni di inversione di tutte le parentesi su una sottostringa di una stringa di parentesi sono necessarie per rendere la stringa "corretta"?

Question

Chiamo una stringa di parentesi "corretta" se ogni parentesi di apertura ha una parentesi di chiusura corrispondente da qualche parte dopo di essa e ogni parentesi di chiusura ha una parentesi di apertura corrispondente da qualche parte prima di essa.Per esempio

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

è una stringa corretta e

)()()(

è una stringa errata.

Un'operazione consiste nel prendere una sottosequenza contigua della stringa di input e 'capovolgere' ogni parentesi in quella sottosequenza.

Data una stringa arbitraria di parentesi (di lunghezza pari), il compito è trovare il minor numero di operazioni di questo tipo necessarie per trasformarla in una stringa di parentesi "corretta".

Un altro modo di affrontare questo problema è avere una stringa di +1 e -1 e cercare di trovare il minor numero di operazioni (di moltiplicare ogni numero su un intervallo per -1) necessarie per rendere ogni prefisso di questa stringa non negativo e ogni suffisso non positivo.

Answer 1

Il DP ha suggerito nei commenti di Yuval Filmus funziona davvero: possiamo risolvere il problema in $ \ mathcal {o} (n ^ {2}) $ DP.

Prima nota che potremmo supporre che gli intervalli non siano autorizzati a sovrapporsi. Prendi due intervalli di sovrapposizione $ [a, b) $ e $ [c, d) $ . Wlog $ a \ leq c $ . Quindi possiamo sostituire i due intervalli con gli intervalli $ [A, c) $ e $ [\ min (B, D ), \ max (B, D)) $ che non si sovrappongono, hanno lunghezza totale più breve e coprire esattamente gli stessi elementi.

Sostituire le staffe di apertura con $ 1 $ , staffe di chiusura con $ - 1 $ . Ora il problema corrisponde all'applicazione del numero minimo di operazioni "Intervallo multiplica di $ - 1 $ " Tale che ogni prefisso ha una somma non negativa e la somma sull'intero array è zero.

Costruiamo una soluzione da sinistra a destra. In ogni posizione possiamo iniziare un intervallo, o terminare un intervallo attivo.

Let $ DP [m] [s] [0] $ Dennare il numero minimo di intervalli che dobbiamo usare tale che ogni somma di prefisso nel primo $ m $ Elementi non è negativo, la somma della prima $ m $ elementi è $ S $ e non abbiamo un intervallo attivo. Allo stesso modo $ DP [m] [s] [1] $ è lo stesso valore in cui abbiamo un intervallo attivo.

Se la $ m $ il valore è $ 1 $ , per $ 0 \ Leq S \ Leq m $ Impostato

.
• $ DP [m] [s] [0]= DP [M-1] [S-1] [0] $
• $ DP [m] [s] [1]= DP [M-1] [S + 1] [1] $

Altrimenti impostiamo

.
• $ DP [m] [s] [0]= DP [M-1] [s + 1] [0] $
• $ DP [m] [s] [1]= DP [M-1] [S-1] [1] $ .

Quindi finiamo e avviando intervalli, impostazione

.
• $ 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) $

Il caso base è $ DP [0] [0] [0]= 0 $ , $ DP [0 ] [0] [1]= 1 $ .

Ci sono $ \ mathcal {o} (n ^ {2}) $ afferma, e facciamo $ \ Mathcal {o} (1) $ Lavora per calcolare ciascuno di essi, quindi l'algoritmo funziona in $ \ mathcal {o} (n ^ {2}) $ . Il DP può essere implementato per utilizzare $ \ mathcal {o} (n) $ memoria memorizzando solo i valori di $ DP $ per la corrente $ m $ .

Ecco un'implementazione C ++ dell'algoritmo.

#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';
}

.

Answer 2

Bella domanda!

Ecco il problema in termini più popolari.

Parentesi bilanciate

Una stringa di parentesi è bilanciata se possiamo cambiarla in una stringa vuota rimuovendo ripetutamente le sottostringhe "()".Ad esempio, la stringa vuota "()" e "(())()((()()))" sono bilanciate ma nessuno di "())" e ")()()(" è bilanciato.

È chiaro che una stringa bilanciata deve iniziare con "(" e terminare con ")".Deve essere anche di lunghezza uniforme.

il problema delle operazioni minime per bilanciare una stringa

Permettere s essere una stringa non vuota di parentesi di lunghezza n.L'unica operazione che possiamo eseguire è invertire ogni parentesi in una sottostringa, ovvero cambiare ogni "(" in ")" e ogni ")" in "(" per alcuni caratteri contigui nella stringa.Il problema è come trovare il minor numero di operazioni possibili s equilibrato.

un approccio di programmazione dinamica

Quali sono i sottoproblemi appropriati?Sono dp[i][j] per 0 <= i < j < n, Dove dp[i][j] è il numero minimo di operazioni che bilanciano la sottostringa tra indice i e indice j compreso.Il numero minimo desiderato di operazioni che si bilanciano s È dp[0][n-1].

Poiché qualsiasi stringa di lunghezza dispari non può essere bilanciata, d'ora in poi limiteremo la nostra attenzione alle stringhe di lunghezza pari.

i casi base dp[i][i+1] è 0 se la sottostringa tra i E i+1 è bilanciato, cioè "()".Altrimenti è 1.

la relazione di ricorrenzaUtilizzerò Java per definire la relazione di ricorrenza.

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;
}

La relazione di ricorrenza deriva dalla seguente proprietà ben nota delle stringhe bilanciate.Una stringa non vuota è bilanciata se e solo se è la concatenazione di due stringhe bilanciate oppure "(" seguito da una stringa bilanciata seguita da ")".

Il trattamento prima del for ciclo, che imposta min essere dp[i + 1][j - 1] più 0, 1 o 2, deriva dal fatto che "(" seguito da una stringa bilanciata seguita da ")" deve essere una stringa bilanciata.

L'elaborazione in for loop, che tenta di restringersi min A dp[i][k] + dp[k + 1][j] meno 0 o 1 per alcuni k quello è tra i E j, deriva dal fatto che la concatenazione di due stringhe bilanciate deve essere una stringa bilanciata.

La complessità temporale di questo approccio è $O(n^3)$.La complessità spaziale è $O(n^2)$.

Lunghezza delle corde "più sbilanciate".

La lunghezza più piccola di una stringa che non può essere bilanciata con meno di 2 operazioni è 4.Per esempio, ")((("

La lunghezza più piccola di una stringa che non può essere bilanciata con meno di 3 operazioni è 10.Per esempio, ")(((((())("

La lunghezza minima di una stringa che non può essere bilanciata con meno di 4 operazioni è 22.Per esempio, ")(())))(((((((((((())(".

Domanda:Qual è la lunghezza più piccola di una stringa che richiede almeno 5 operazioni?Come ho calcolato, deve essere maggiore di 28.Tuttavia, i miei calcoli non sono sufficienti per determinare il valore effettivo.Quanto velocemente possiamo calcolare queste lunghezze più piccole?