Это обсуждение публикации https://olympiads.bc-pf.org/informatics/national/2022
Можете подсказать, как решить Дшку респы? Решил на 39 баллов, а дальше не идёт.
Подсказка: Перебирем x, минимальное за которую заплатим
Не понимаю как это делать. Можно еще подсказки?
Перебери x, пусть ты не платишь за всё что \leq x. Сделай для каждого элемента так a_{i,j} = max(0, a_{i, j} - x), дальше что делать подумай сам
2 лайка
Пусть dp[n][m] - это за максимальная цена, которую нужно платить, чтобы прийти в клетку {n; m}. Значит, будем перебирать x до того момента, когда dp[n][m] будет равно 0? Если да, то восстанавливаем путь дп и берем k максимальных значений?
А, ой. Путь же не всегда один
1 лайк
Можно бинарить x и выбрать минимальное значение x когда dp[n][m] = 0. Но как находить путь оптимально (т.е. когда сумма k максимальных элементов минимальна)?
нельзя
Если нету мыслей то тут будет решение, можешь открыть если хочешь
В этой таблице найди dp_{i,j}
Добавь к dp_{n, m} k * x, это и будет ответ для x, почему это работает пруфани сам
1 лайк
Извините, не до конца понял
Какая тут формула для dp[i][j]? Это минимальный путь? Еще прибавляем k*x только когда dp[n][m] = 0?
1 лайк
Да
Нет
1 лайк
Советую отложить задачу если сложно понять, поставить напоминание и позже вернуться.
1 лайк
Тупанул
Да, я понял решение. Спасибо