Neerc

Можете подсказать, как решить Дшку респы? Решил на 39 баллов, а дальше не идёт.

Nursik

Подсказка: Перебирем x, минимальное за которую заплатим

1 ответ

Neerc

Не понимаю как это делать. Можно еще подсказки?

1 ответ

Zhabka

Перебери x, пусть ты не платишь за всё что \leq x. Сделай для каждого элемента так a_{i,j} = max(0, a_{i, j} - x), дальше что делать подумай сам

3 ответа

Neerc

Пусть dp[n][m] - это за максимальная цена, которую нужно платить, чтобы прийти в клетку {n; m}. Значит, будем перебирать x до того момента, когда dp[n][m] будет равно 0? Если да, то восстанавливаем путь дп и берем k максимальных значений?

1 ответ

Neerc

А, ой. Путь же не всегда один

Neerc

Можно бинарить x и выбрать минимальное значение x когда dp[n][m] = 0. Но как находить путь оптимально (т.е. когда сумма k максимальных элементов минимальна)?

1 ответ

Zhabka

нельзя

Zhabka

Если нету мыслей то тут будет решение, можешь открыть если хочешь (нажмите для более подробной информации) 1 ответ

Neerc

Извините, не до конца понял
Какая тут формула для dp[i][j]? Это минимальный путь? Еще прибавляем k*x только когда dp[n][m] = 0?

2 ответа

Zhabka

Да

Нет

Zhabka

Советую отложить задачу если сложно понять, поставить напоминание и позже вернуться.

1 ответ

Neerc

Тупанул
Да, я понял решение. Спасибо