Изменения

Перейти к: навигация, поиск
м
Описание алгоритма
Сделаем предподсчёт действия каждого возможного квадрата. Окончательный результат зависит только от значений в верхнем левом «уголке» над квадратом и подстрок, для которых считается ответ {{---}} остальные значения в квадрате однозначно считаются с их помощью. Окончательным результатом будут значения в нижнем правом «уголке» квадрата.
Может показаться, что таких уголков может быть много. Но, так как соседние числа в матрице отличаются не более, чем на один, то результат зависит только от константы в верхнем левом элементе матрицы, и возрастания чисел в верхнем и левом крае квадрата. Возрастание чисел будем хранить с помощью битовых масок: сначала <tex> k - 1 </tex> бит кодирует возрастание чисел в верхнем крае квадрата (<tex>0 </tex> {{---}} элемент равен предыдущему, <tex>1 </tex> {{---}} больше предыдущего на один), потом <tex> k - 1 </tex> бит кодируют возрастание чисел в квадрате по левому краю аналогичным образом.
Более того, константу в верхнем левом элементе квадрата можно вообще не хранить: её можно прибавить при необходимости к каждому элементу результата.
Посчитаем эти квадраты для строк <tex>abbabb </tex> и <tex>bababb</tex>. Возьмём <tex> k = 3 </tex>. Тогда предподсчитанные квадраты, которые понадобятся для дальнейшего вычисления НОП, выглядят так:
{|
65
правок

Навигация