|
|
|
|
|
|
|
Вернуться
| 1 Ван Пан Впп, 11 марта 2024 г. 17:59:08 | |
https://text.ru/
[url]https://text.ru/[/url]
[url=https://text.ru/]https://text.ru/[/url]
<a href="https://text.ru/">https://text.ru/</a>
[https://text.ru/](https://text.ru/)
|
|
|
| 2 Холи, 09 декабря 2023 г. 9:07:43 | |
|
Огромное срасибо за такой подробный разбор
|
|
|
| 3 Тер-Саркисов Богдан Олегович, 08 декабря 2023 г. 21:45:50 | |
...Для этого надо заметить следующее: в оптимальном разбиении нет групп размера 4 и больше.
Обосновывается это тем, что такую группу можно разбить на непересекающиеся по диапазону значений группы меньшего размера, что не ухудшит ответ.
Тогда значение k в формуле надо перебирать в диапазоне [2; 3]. То есть dp[n] = min(max(dp[n-2], a[n-1]-a[n-2]), max(dp[n-3], a[n-1]-a[n-3])).
|
|
|
| 4 Тер-Саркисов Богдан Олегович, 08 декабря 2023 г. 21:45:11 | |
1) Утверждается, что эффективное разбиение следует искать в сортированном массиве в виде наборов рядом стоящих элементов.
Например, если имеется сортированный массив a = [1, 4, 6, 9, 13], то эффективно разбить на две группы [1, 4, 6] и [9, 13].
Как это доказывается? Пусть имеется некоторое разбиение массива на группы. Возьмём какие-то две группы.
Пусть минимальный и максимальный элементы этих групп равны соответственно min1, max1 и min2, max2.
Ответ для выбранного разбиения вычисляется как максимум между значениями разности максимального и минимального элементами в группах.
То есть max(..., max1-min1, max2-min2).
Пусть диапазоны [min1; max1] и [min2; max2] пересекаются.
а) Пересечение такого вида: min1 <= min2 <= max2 <= max1. Тогда ответ не ухудшится, если две группы объединить в одну: [min1,...,min2,...,max2,...,max1].
б) Пересечение такого вида: min1 <= min2 <= max1 <= max2. Тогда ответ не ухудшится, если группа 1 будет поглощать из группы 2 все элементы,
начиная с min2, до тех пор, пока в группе 2 есть больше двух элементов, а группы 1 и 2 будут пересекаться по диапазону значений.
Если группы по-прежнему пересекаются по диапазону значений, то есть в группе 2 ровно два элемента, то тогда обменять элементы max1' и min2' новых групп, что тоже не ухудшит ответ.
Конец доказательства.
Теперь подключаем подход динамического программирования. Пусть dp[n] - минимальная разговорчивость для префикса размера n (сортированного) массива a.
Для вычисления dp[n] можно перебрать все возможные размеры k последней группы в разбиении и выбрать минимальный ответ.
dp[n] = min(max(dp[n-k], a[n-1]-a[n-k]) for k in range(2,...)).
Стоит учесть базовые случаи: dp[0], dp[1] не определены; dp[2] = a[1] - a[0]; dp[3] = a[2] - a[0] (если n >= 3); dp[4] = max(a[1]-a[0], a[3]-a[2]) (если n >= 4).
Это решение за O(n^2), которое с заданными ограничениями может пройти по времени.
2) Представленная вами формула из комментариев - улучшенная версия текущего решения, позволяющая решить задачу за O(n).
Для этого надо заметить сл
|
|
|
| 5 Холи, 08 декабря 2023 г. 17:16:37 | |
|
Не совсем понимаю почему нужен min в формуле(dp[i] = min(max(t[i] - t[i - 1], dp[i - 2]), max(t[i] - t[i - 2], dp[i - 3])); ) идея: для того ,что бы масив делился на минимальные группы, но почему-то возникает сомнение
|
|
|
| 6 Терентьев Михаил Павлович, 06 декабря 2023 г. 22:07:52 | |
|
Там в комментариях готовая формула динамики имеется. Но к ней надо придти с помощью несложных идей, писать про которые, наверное, будет медвежьей услугой.
|
|
|
| 7 Холи, 06 декабря 2023 г. 21:34:25 | |
|
186 задача уже голова кипит, никак не научусь решать динамику
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
