كم عدد عمليات التقليب كل الأقواس على سلسلة فرعية من سلسلة من الأقواس هناك حاجة لجعل سلسلة 'الصحيح'?

Question

أدعو سلسلة من الأقواس 'الصحيح' إذا كان كل قوس افتتاح لديه قوس إغلاق المقابلة في مكان ما بعد ذلك وكل قوس إغلاق لديه قوس افتتاح المقابلة في مكان ما قبل ذلك.على سبيل المثال

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

هي سلسلة صحيحة و

)()()(

هي سلسلة غير صحيحة.

عملية تتكون من اتخاذ لاحقة متجاورة من سلسلة الإدخال و 'التقليب' كل قوس في تلك اللاحقة.

وبالنظر إلى سلسلة تعسفية من الأقواس (حتى طول) ، والمهمة هي العثور على أصغر عدد من هذه العمليات اللازمة لتغييره إلى سلسلة 'الصحيح' من الأقواس.

هناك طريقة أخرى للنظر إلى هذه المشكلة وهي أن يكون لديك سلسلة من +1 ثانية و -1 ثانية ، ومحاولة العثور على أصغر عدد من العمليات (بضرب كل رقم على فاصل زمني في -1) اللازمة لجعل كل بادئة من هذه السلسلة غير سالبة وكل لاحقة غير إيجابية.

Answer 1

DP المقترح في التعليقات التي يعمل بها Yuval Filmus بالفعل: يمكننا حل المشكلة في $ \ mathcal {o} (n ^ {{2}) $ بواسطة موانئ دبي.

لاحظ أولا أننا قد نفترض أن الفواصل غير مسموح بها للتداخل. خذ أي فواصل زمنية متداختين $ [a، b) $ و $ [c، d) $ . WLOG $ a \ leq c $ . ثم يمكننا استبدال الفواصل الزمنية مع الفواصل الزمنية $ [a، c) $ و $ [\ min (b، d )، \ Max (B، D)) $ التي لا تتداخل، لديها طول إجمالي أقصر وتغطي بالضبط نفس العناصر.

استبدال أقواس فتح مع $ 1 $ ، إغلاق الأقواس مع $ - 1 $ . الآن المشكلة تتوافق مع تطبيق الحد الأدنى لعدد العمليات "مضاعفة الفاصل الزمني بواسطة $ - 1 $ " بحيث يكون لكل بادئة مبلغ غير ناعم، والمجموع عبر الصفيف بأكمله هو صفر.

نبني حلا من اليسار إلى اليمين. في كل موقف يمكننا إما بدء فاصل زمني، أو إنهاء فاصل زمني نشط.

دع DP [M] [S] [0] $ تدل على الحد الأدنى لعدد فتراتنا نحتاج إلى استخدامه بحيث كل مبلغ بادئة في الأول $ M $ العناصر غير نقطية، مجموع $ m $ العناصر هي $ S $ ، وليس لدينا فاصل زمني نشط. وبالمثل DP $ [M] [S] [1] $ هي نفس القيمة التي لدينا فاصل زمني نشط.

إذا كانت $ m $ th value هي $ 1 $ ، ل $ 0 \ leq s \ leq m $ تعيين

• DP [م] [م] [0]= DP [M-1] [S-1] [0] $
• DP [م] [م] [1]= DP [M-1] [S + 1] [1] $

خلاف ذلك وضعنا

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

ثم ننتهي وبدء الفترات، وإعداد

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

القضية الأساسية هي $ DP [0] [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 ++ للخوارزمية.

giveacodicetagpre.

Answer 2

سؤال جميل!

هنا هي المشكلة في شروط أكثر شعبية.

الأقواس المتوازنة

يتم موازنة سلسلة من الأقواس إذا تمكنا من تغييرها إلى السلسلة الفارغة عن طريق إزالة السلاسل الفرعية "()" بشكل متكرر.على سبيل المثال ، سلسلة فارغة ، "() " و "(())()((()()))" متوازنة ولكن لا يوجد أي من "())" و ")()()(" متوازن.

من الواضح أن السلسلة المتوازنة يجب أن تبدأ بـ "(" وتنتهي بـ ")".يجب أن يكون حتى طول كذلك.

مشكلة الحد الأدنى من العمليات لتحقيق التوازن بين سلسلة

دعونا 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 خلاف ذلك.

علاقة التكرار وسوف تستخدم جافا لتحديد العلاقة تكرار.

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 ال (ن^3)).تعقيد الفضاء هو O ال (ن^2)).

طول الأوتار "الأكثر توازنا"

أصغر طول لسلسلة لا يمكن موازنتها بأقل من 2 عملية هو 4.على سبيل المثال،") ((("

أصغر طول لسلسلة لا يمكن موازنتها بأقل من 3 عمليات هو 10.على سبيل المثال, ")(((((())("

أصغر طول لسلسلة لا يمكن موازنتها بأقل من 4 عمليات هو 22.على سبيل المثال, ")(())))(((((((((((())(".

السؤال:ما هو أصغر طول السلسلة التي تحتاج على الأقل 5 عمليات?كما حسبت ، يجب أن يكون أكبر من 28.ومع ذلك ، فإن حسابي لا يكفي لتحديد القيمة الفعلية.مدى سرعة يمكننا حساب هذه أصغر أطوال?