|
|
|
|
|
|
|
| 1 Воробьев Григорий Артёмович, 24 марта 2026 г. 18:36:37 |
| Можно решать не через большой dp[n][m], а через DP по цепочкам делений. Для каждой стороны сохраняем только реально достижимые размеры: n -> ceil(n/2) -> ... -> 1 и m -> ceil(m/2) -> ... -> 1. Тогда состояние — это не сам прямоугольник n x m, а (i, j), где i и j — сколько раз уже делили первую и вторую сторону. Из каждого состояния только 2 перехода: делить дальше по первой стороне или по второй. Если текущая делимая сторона нечётная, доплата равна длине другой стороны. Так состояний получается всего O(log n * log m), и решение спокойно проходит даже на Python. Если у кого-то на полном dp[n][m] были странные Runtime error, такой вариант обычно это убирает.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
