Подозрительные отчеты

Автор задачи и разработчик: Мария Жогова

Рассмотрим классическую динамику для задачи нахождения наибольшей общей последовательности. В данном случае мы хотим проверить, что сокращенный отчет целиком «входит» в полный отчет с указанными дополнительными ограничениями. Будем хранить $$$\mathtt{dp}[i][j]$$$ — могут ли первые $$$i$$$ столбцов гистограммы полного отчета содержать первые $$$j$$$ столбцов противозаконного отчета, чтобы $$$i$$$-й соответствовал $$$j$$$-му.

При пересчете такой динамики достаточно перебрать $$$k$$$ — предыдущий столбец первой гистограммы, соответствующий $$$j-1$$$-му столбцу второй. На него накладываются следующие ограничения: $$$s_k - t_{j-1} = s_i - t_j$$$ (то, что гистограмма была обрезана по горизонтальной линии, означает, что разности высот столбцов одинаковы) и $$$s_x \leqslant s_i - t_j$$$ для всех $$$k < x < i$$$ (так как все элементы между выбранными столбцами должны быть не выше линии разреза). Таким образом, $$$$$$\mathtt{dp}[i][j] = \bigvee \limits_{\substack{k < i \\ s_k - t_{j-1} = s_i - t_j \\ \max \limits_{k < x < i} s_x < s_i - t_j}} \mathtt{dp}[k][j - 1]$$$$$$

Такой пересчет в наивной реализации работает за $$$\mathcal{O}(n m^2)$$$. Для этого достаточно во вложенных циклах по $$$i$$$ и $$$j$$$ перебирать $$$k$$$ по убыванию от $$$i$$$ до $$$0$$$, поддерживать максимум на отрезке от $$$k + 1$$$ до $$$i - 1$$$ и проверять описанные условия. Решение с такой асимптотикой проходило по времени.