Условие
Приведённое решение
предыдущей задачи требует порядка
mn2 действий. Придумать способ с числом действий
порядка
mn.
Подсказка
Придётся пожертвовать симметрией и выбрать одну из строк за
основную. Двигаясь по основной строке, поддерживаем такое
соотношение: во всех остальных строках отмечен максимальный
элемент, не превосходящий текущего элемента основной
строки.
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
2 |
|
Название |
Массивы |
|
задача |
|
Номер |
1.2.26 |
