Wie viele Operationen zum Umdrehen aller Klammern in einer Teilzeichenfolge einer Klammerfolge sind erforderlich, um die Zeichenfolge „richtig“ zu machen?

Question

Ich nenne eine Klammerfolge „korrekt“, wenn hinter jeder öffnenden Klammer irgendwo eine entsprechende schließende Klammer steht und vor jeder schließenden Klammer irgendwo davor eine entsprechende öffnende Klammer steht.Zum Beispiel

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

ist eine korrekte Zeichenfolge und

)()()(

ist eine falsche Zeichenfolge.

Eine Operation besteht darin, eine zusammenhängende Teilsequenz der Eingabezeichenfolge zu nehmen und jede Klammer in dieser Teilsequenz umzudrehen.

Bei einer beliebigen Klammerfolge (gerader Länge) besteht die Aufgabe darin, die kleinste Anzahl solcher Operationen zu finden, die erforderlich ist, um sie in eine „richtige“ Klammerfolge zu ändern.

Eine andere Möglichkeit, dieses Problem zu betrachten, besteht darin, eine Zeichenfolge mit +1 und -1 zu haben und zu versuchen, die kleinste Anzahl von Operationen (Multiplikation jeder Zahl in einem Intervall mit -1) zu finden, die erforderlich sind, um jedes Präfix dieser Zeichenfolge nicht negativ zu machen und jedes Suffix nichtpositiv.

Answer 1

Der DP, der in den Kommentaren von Yuval Filmus vorgeschlagen wird, funktioniert in der Tat: Wir können das Problem in $ \ Mathcal {O} lösen (n ^ {2}) $ von Dp.

Erster Hinweis darauf, dass wir davon ausgehen, dass sich die Intervalle nicht überlappen dürfen. Nehmen Sie zwei überlappende Intervalle $ [a, b) $ und $ [c, d) $ . WLOG $ A \ LEQ C $ . Dann können wir die beiden Intervalle durch die Intervalle ersetzen $ [a, c) $ und $ [\ min (b, d ), \ max (b, d)) $ , die nicht überlappen, kürzere Gesamtlänge haben und genau die gleichen Elemente abdecken.

Öffnungswinkel ersetzen mit $ 1 $ , Schließklammern mit $ - 1 $ . Nun entspricht das Problem der Anwendung der Mindestanzahl der Operationen "Multiplde Intervall" mit $ - 1 $ ", so dass jedes Präfix nicht negative Summe hat, und die Summe über dem gesamten Array ist Null.

Wir erstellen eine Lösung nach links nach rechts. In jeder Position können wir entweder ein Intervall starten oder ein aktives Intervall beenden.

$ dp [m] [s] [s] [0] $ Bezeichnen Sie die Mindestanzahl der Intervalle, die wir verwenden müssen, so dass jede Präfix-Summe in der ersten $ M $ Elemente ist nichtnegativ, die Summe der ersten $ M $ Elemente ist $ s $ , und wir haben kein aktives Intervall. In ähnlicher Weise ist $ dp [m] [s] [1] $ ist der gleiche Wert, in dem wir ein aktives Intervall haben.

Wenn der $ M $ th Wert ist $ 1 $ , für $ 0 \ LEQ S \ LEQ M $ Wir setzen

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

Ansonsten setzen wir

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

dann enden und starten Sie Intervalle, Setting

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

Der Basisfall ist $ dp [0] [0] [0]= 0 $ , $ dp [0 ] [0] [1]= 1 $ .

Es gibt $ \ Mathcal {O} (n ^ {2}) $ , und wir machen $ \ Mathcal {O} (1) $ Arbeit, um jeden von ihnen zu berechnen, daher läuft der Algorithmus in $ \ Mathcal {O} (n ^ {2}) $ . Der DP kann implementiert werden, um $ \ Mathcal {O} (n) $ Speicher, indem Sie nur die Werte von $ dp speichern $ für den aktuellen $ M $ .

Hier ist eine C ++ - Implementierung des Algorithmus.

generasacodicetagpre.

Answer 2

Gute Frage!

Hier ist das Problem in populäreren Worten ausgedrückt.

Ausgewogene Klammern

Eine Zeichenfolge aus Klammern ist ausgeglichen, wenn wir sie durch wiederholtes Entfernen von Teilzeichenfolgen „()“ in eine leere Zeichenfolge ändern können.Beispielsweise sind die leeren Zeichenfolgen „()“ und „(())()((()()))“ ausgeglichen, aber weder „())“ noch „)()()(“ sind ausgeglichen.

Es ist klar, dass eine ausgeglichene Zeichenfolge mit „(“ beginnen und mit „) enden muss.Außerdem muss es eine gleichmäßige Länge haben.

das Problem minimaler Operationen zum Ausbalancieren einer Saite

Lassen s eine nicht leere Zeichenfolge aus Klammern der Länge sein n.Die einzige Operation, die wir ausführen können, besteht darin, jede Klammer in einer Teilzeichenfolge umzudrehen, d. h. jedes „(“ in „)“ und jedes „)“ in „(“ für einige zusammenhängende Zeichen in der Zeichenfolge zu ändern.Das Problem besteht darin, die kleinste Anzahl von Operationen zu finden, die durchgeführt werden s ausgewogen.

ein Ansatz der dynamischen Programmierung

Was sind die geeigneten Teilprobleme?Sie sind dp[i][j] für 0 <= i < j < n, Wo dp[i][j] ist die minimale Anzahl von Operationen, die den Teilstring zwischen Indizes ausgleichen i und Index j inklusive.Die gewünschte Mindestanzahl von Operationen, die einen Ausgleich ermöglichen s Ist dp[0][n-1].

Da keine Zeichenfolge mit ungerader Länge ausgeglichen werden kann, beschränken wir unsere Aufmerksamkeit von nun an auf Zeichenfolgen mit gerader Länge.

die Basisfälle dp[i][i+1] ist 0, wenn der Teilstring dazwischen liegt i Und i+1 ausgeglichen ist, also „()“.Ansonsten ist es 1.

die WiederholungsrelationIch werde Java verwenden, um die Wiederholungsbeziehung zu definieren.

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

Die Wiederholungsbeziehung ergibt sich aus der folgenden bekannten Eigenschaft ausgeglichener Zeichenfolgen.Eine nicht leere Zeichenfolge ist genau dann ausgeglichen, wenn es sich um die Verkettung zweier ausgeglichener Zeichenfolgen oder „(“ gefolgt von einer ausgeglichenen Zeichenfolge gefolgt von „)“ handelt.

Die Verarbeitung vor dem for Schleife, die setzt min zu sein dp[i + 1][j - 1] plus 0, 1 oder 2 ergibt sich aus der Tatsache, dass „(“ gefolgt von einer ausgeglichenen Zeichenfolge gefolgt von „)“ eine ausgeglichene Zeichenfolge sein muss.

Die Verarbeitung im for Schleife, die versucht zu schrumpfen min Zu dp[i][k] + dp[k + 1][j] für einige minus 0 oder 1 k das liegt dazwischen i Und j, ergibt sich aus der Tatsache, dass die Verkettung zweier ausgeglichener Zeichenfolgen eine ausgeglichene Zeichenfolge sein muss.

Die Zeitkomplexität dieses Ansatzes ist $O(n^3)$.Die Raumkomplexität ist $O(n^2)$.

Länge der „unausgeglichensten“ Saiten

Die kleinste Länge einer Zeichenfolge, die nicht durch weniger als 2 Operationen ausgeglichen werden kann, beträgt 4.Zum Beispiel, ")((("

Die kleinste Länge einer Zeichenfolge, die nicht durch weniger als 3 Operationen ausgeglichen werden kann, beträgt 10.Zum Beispiel, ")(((((())("

Die kleinste Länge einer Zeichenfolge, die nicht durch weniger als 4 Operationen ausgeglichen werden kann, beträgt 22.Zum Beispiel, ")(())))(((((((((((())(".

Frage:Was ist die kleinste Länge einer Zeichenfolge, die mindestens 5 Operationen erfordert?Wie ich berechnet habe, muss es größer als 28 sein.Meine Berechnung reicht jedoch nicht aus, um den tatsächlichen Wert zu ermitteln.Wie schnell können wir diese kleinsten Längen berechnen?