Матч 301, Исправить расстановку скобок (CorrectingParenthesization)

Дивизион 2, Уровень 3

Имеется строка из скобок. Требуется изменить наименьшее количество символов так, чтобы полученная строка была правильной. Удалять или вставлять символы нельзя. Всего существует три вида скобок: (), [] и {}. Правильная строка определяется следующими правилами:

1. Пустая строка является правильной.

2. Если строка s правильная, то правильными являются также (s), [s] и {s}.

3. Если строки s и t правильные, то правильной будет строка st.

Например, строки “([{}])”,“” и “(){}[]” являются правильными, а “([}]”,“([)]” и “{” – нет.

Класс: CorrectingParenthesization

Метод: int getMinErrors(string s)

Ограничения: s содержит от 0 до 50 символов, s содержит четное количество символов ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’.

Вход. Строка символов s.

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

Пример входа

s

"([{}])()[]{}"

"([)]"

"([{}[]"

Пример выхода

0

2

1

РЕШЕНИЕ

динамическое программирование

Обозначим через f(i, j) наименьшее количество символов, которое можно изменить так, чтобы подстрока s_is_i+1…s_j-1s_j стала правильной. Тогда имеют место соотношения:

1. f(i, j) = 0 при i > j, так как в таком случае подстрока будет пустой строкой.

2. f(i, j) = f(i + 1, j – 1) + enc(s_i ,s_j). Делаем так, чтобы символ s_i был открывающейся скобкой, а s_j – соответствующий ему закрывающейся скобкой. Далее рекурсивно рассматриваем подстроку s_i+1…s_j-1.

Функция enc(s_i ,s_j) возвращает:

а) 0, если символы s_i и s_j являются соответствующими открывающейся и закрывающейся скобками;

б) 2, если символ s_i является закрывающейся скобкой, а s_j – открывающейся;

в) 1 иначе. В этом случае достаточно изменить один из символов s_i или s_j так, чтобы они образовали правильную скобочную пару;

3. f(i, j) = (f(i, k) + f(k+1, j)). Подстроку s_is_i+1…s_j-1s_j рассматриваем как последовательность двух правильных скобочных структур: s_i…s_k и s_k+1…s_j.

В ячейках m[i][j] массива m сохраняем значения f(i, j). Ответом задачи будет f(0, |s| – 1), где s – входная строка.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <memory>

#define min(i,j) (i < j) ? i : j

using namespace std;

int m[51][51];

string s;

int enc(char c, char d)

{

string p = "([{)]}";

if (p.find(c) / 3 > 0 && p.find(d) / 3 < 1) return 2;

if (p.find(c) % 3 == p.find(d) % 3 && c != d) return 0;

return 1;

}

int f(int i, int j)

{

int k;

if (i > j) return 0;

if (m[i][j] >= 0) return m[i][j];

int r = f(i+1,j-1) + enc(s[i],s[j]);

for(k = i + 1; k < j; k += 2)

r = min(r,f(i,k) + f(k+1,j));

return m[i][j] = r;

}

class CorrectingParenthesization

{

public:

int getMinErrors(string s)

{

::s = s;

memset(m,-1,sizeof(m));

return f(0,s.size() - 1);

}

};