Шов через пиксель
В фоторедакторе есть кнопка «убрать предмет»: пользователь показывает пиксель, а редактор подсказывает, во что обойдётся вырезать шов через него. Шов — по одному пикселю в каждой строке сверху донизу, пиксели соседних строк стоят в одном столбце или в соседних, энергия шва — сумма энергий его пикселей. Для каждого показанного пикселя найдите наименьшую энергию шва, который через него проходит.
Третий тест — настоящая фотография автора сайта шириной 120 пикселей, и в нём спрашивают про каждый пиксель.
Вход
В первой строке высота H и ширина W (1 ≤ H, W; H·W ≤ 2,5·105). Дальше H строк по W целых чисел от 0 до 1530 — энергии пикселей. Затем число вопросов q (1 ≤ q ≤ 105) и q строк r c — строка и столбец пикселя, с единицы.
Выход
Для каждого вопроса — наименьшая энергия шва через этот пиксель.
Примеры
Пример 1
7 10 37 58 68 73 48 100 79 90 84 95 104 63 76 61 58 68 89 101 92 64 76 58 79 83 89 100 110 84 84 87 75 118 104 70 60 48 35 28 35 44 333 371 272 109 61 107 99 163 150 65 289 166 355 263 156 162 207 214 237 183 311 411 267 109 92 138 163 212 197 94 5 1 1 5 1 7 5 4 10 6 2
558 999 552 618 954
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Один вопрос решается таблицей самого дешёвого шва, где в строке r разрешён только пиксель c. Но таблица стоит H·W шагов, и сто тысяч таблиц — это 2,5·1010. Что в этих таблицах общего?
2Подсказка 2
Шов через пиксель (c, r) состоит из двух половин: сверху до пикселя и от пикселя донизу. Зависят ли эти половины друг от друга?
3Идея
Половины независимы: верхней части шва всё равно, как он пойдёт ниже пикселя, и наоборот. Значит, лучший шов через пиксель — лучший шов сверху до него плюс лучший шов снизу до него. Посчитаем две таблицы: down[y][x] — самый дешёвый шов от верхней строки до пикселя, как в seam carving, и up[y][x] — то же от нижней строки. Ответ на вопрос — down[r][c] + up[r][c] − E[r][c]: сам пиксель вошёл в обе половины.
4Разбор
Таблица up — та же таблица, что down, только для снимка, перевёрнутого вверх ногами: в Python достаточно развернуть список строк, посчитать и развернуть результат обратно. Дальше каждый вопрос — три обращения к массивам.
Приём «посчитать заранее с двух концов и склеить в точке» встречается часто: так находят самый дешёвый путь через заданную вершину графа или число кратчайших путей, которые через неё проходят. Он работает всякий раз, когда два куска ответа не мешают друг другу.
4+Решение
5Сложность
O(H·W + q) времени и O(H·W) памяти: две таблицы и по O(1) на вопрос.
6Типичные ошибки
- Своя таблица на каждый вопрос. Верно, но уже третий тест — 7320 вопросов про фото 120 × 61, а в больших тестах вопросов до ста тысяч.
- Пиксель посчитан дважды. Без вычитания E[r][c] ответ больше правильного на энергию самого пикселя.
- Шов «снизу» по таблице сверху. down[H−1] знает лучшие швы, кончающиеся в нижней строке, но не лучший путь вниз от данного пикселя: нужна отдельная таблица.