Форум Всеукраїнської інтернет-олімпіади NetOI

Предлагаю вашему вниманию решение задачи Bracket на 100 процентов.  // Онлайн проверка на всех тестах уже работает для этой задачи

Немного пояснения:

Заведем двойной массив в котором мы будем динамически считать ответ к задаче. Номер строки в очередном столбле - количество открытых скобок, которые еще не закрыты. Количество столбцов = общее количество символов. Назовем массив d. Тогда если на очередном шаге скобка является открывающей (номер скобки обозначим через i), то в j-ой строке i-ого столбца будет такой результат:
d[i, j] := d[i - 1, j] + d[i - 1, j - 1]
Это объясняется тем, что для того, чтобы на данном шаге было j открывающих скобок необходимо либо зачеркнуть открывающюю скобку, либо оставить ее (либо оставить j таким, как есть, либо увеличить).

Если на очередном шаге скобка является закрывающей (номер скобки обозначим через i), то в j-ой строке i-ого столбца будет такой результат:
d[i, j] := d[i - 1, j] + d[i - 1, j + 1]
Это объясняется тем, что для того, чтобы на данном шаге было j открывающих скобок необходимо либо зачеркнуть закрывающюю скобку, либо оставить ее (либо оставить j таким, как есть, либо уменьшить).

Если на очередном шаге скобка является квадратной закрывающей (номер скобки обозначим через i), то в 0-ой строке i-ого столбца будет такой результат:
d[i, 0] := d[i - 1, 0] + d[i - 1, 1] + ... + d[n - 1, m];
где m - общее количество открывающих скобок которые стоят до данной.
Это объясняется тем, что для того, чтобы на данном шаге было 0 открывающих скобок необходимо оставить квадратную закрывающую скобку (перейти в это состояние мы можем закрыв любое количество открывающих скобок).

Если на очередном шаге скобка является квадратной закрывающей (номер скобки обозначим через i), то в j-ой строке i-ого столбца (j > 0) будет такой результат:
d[i, j] := d[i - 1, j];
Это объясняется тем, что для того, чтобы на данном шаге было j открывающих скобок необходимо зачеркнуть квадратную закрывающую скобку (при этом результат в j-той строке не меняется, для j > 0, поскольку квадратная скобка на эти строки не воздействует).

d[0, 0] = 1, поскольку из пустуой строки сделать правильное скобочное выражение можно одним способом.

Ответ на задачу будет храниться в d[n, 0], где n - количество скобок.

Также очевидной является оптимизация для использования одного столбца вместо n, то есть одномерного массива, вместо двумерного (хранить ответ только для текущего шага).


Собственно код моего решения:

program Bracket;

const
  MODULE = 1000007;
  MAX_N = 1000;

var
  d: array [0..MAX_N] of int64;
  c: char;
  i, j: longint; // i и j не соответствуют тем, что описаны выше

begin
  d[0] := 1;
  j := 1;
  while true do
  begin
    read(c);
    case c of
      '(':
      begin
        for i := j downto 0 do
          d[i + 1] := (d[i + 1] + d[i]) mod MODULE;
        inc(j);
      end;
      ')':
        for i := 1 to j do
          d[i - 1] := (d[i - 1] + d[i]) mod MODULE;
      ']':
        for i := 1 to j do
          d[0] := (d[0] + d[i]) mod MODULE;
      else
        break;
    end;
  end;
  writeln(d[0]);
end.

Если что-то непонятно - пишите. // Прошу не задавать глупых вопросов

Відредаговано traveller6 (2014-02-07 10:14:21)