"Поле чудес"#78

"Поле чудес" (Editorial)

Це класична задача динамічного програмування на таблиці.

Позначимо через максимальну суму, яку можна набрати на шляху з лівої верхньої клітинки до клітинки . Оскільки в клітинку можна потрапити лише зверху, зліва або по діагоналі зверху-зліва, отримуємо

\mathrm{dp}[i][j] = A[i][j] + \max\bigl(\mathrm{dp}[i-1][j],\; \mathrm{dp}[i][j-1],\; \mathrm{dp}[i-1][j-1]\bigr),

де максимум береться лише по тих варіантах, які не виходять за межі поля.

База — \mathrm{dp}[1][1] = A[1][1]. Перший рядок і перший стовпець заповнюються окремо: туди можна дійти єдиним способом, тому там просто накопичується префіксна сума.

Відповідь — \mathrm{dp}[N][M]. Якщо це число додатне, Степан виграв, і в першому рядку виводимо winner, інакше — loser. У другому рядку виводимо саму суму.

Важлива деталь: числа в клітинках можуть бути від'ємними, тому ініціалізувати нулями не можна — використовуйте «мінус нескінченність» для недосяжних станів або акуратно обробіть межі. Сума нуль означає програш, бо умова вимагає саме додатну суму.

Складність — , тобто щонайбільше 10^4 операцій.