Комментарии 11
Почему пример жадного алгоритма на рисунке неверен? Осталось 3 дуба, это наилучшее решение. 4 дуба из пяти оставить невозможно.
в данном случае, да. но если взять первый дуб как 2 метра, то жадина не прокатит.
Там имелось ввиду, что не прокатит удалить все дубы жадиной.
Обновил контрпример к жадному алгоритму. Теперь там вообще остаётся некорректное решение.
Трабла с одинаковыми соседними дубами. Если такие в ходе решения получаются, то убрать эту пару уже невозможно.
Как решать если в примере 3 и 4-й дубы будут по единице, а нулевой равен двойке.
Как решать если в примере 3 и 4-й дубы будут по единице, а нулевой равен двойке.
Какой-то оверкилл, задача решается за O(N^2)
1. Простым ДП находим список дубов, которые нужно убрать — O(N^2) операций.
2. Делаем связанный список из всех деревьев с пометками на уничтожения, и проходим по нему несколько раз, уничтожая помеченные деревья, у которых соседи строго больше или строго меньше. На каждом проходе уничтожается как минимум одно дерево, так что надо O(N) проходов по O(N) операций.
1. Простым ДП находим список дубов, которые нужно убрать — O(N^2) операций.
2. Делаем связанный список из всех деревьев с пометками на уничтожения, и проходим по нему несколько раз, уничтожая помеченные деревья, у которых соседи строго больше или строго меньше. На каждом проходе уничтожается как минимум одно дерево, так что надо O(N) проходов по O(N) операций.
В такоем случае, странно, что дали задачу с ограничением n<=200. Могли бы дать n<=1000 и сказать, что на 60 баллов будет решение за куб.
Даже если в первый пункт поверить (что Вы сумеете найти такую подпоследовательность, что элементы между можно удалить), у Вас свалится жадина во втором пункте. Тест:
1 4 5 3 6 3 2 — ответ, очевидно, 1 2
1 4 x 3 6 3 2
1 x x 3 6 3 2
1 x x 3 x 3 2
А как правильно:
1 4 5 3 6 3 2
1 4 5 x 6 3 2
1 4 5 x x 3 2
1 4 x x x 3 2
1 x x x x 3 2
1 x x x x x 2
Добавлю в статью вместо спорного примера. Спасибо большое.
Даже если в первый пункт поверить (что Вы сумеете найти такую подпоследовательность, что элементы между можно удалить), у Вас свалится жадина во втором пункте. Тест:
1 4 5 3 6 3 2 — ответ, очевидно, 1 2
1 4 x 3 6 3 2
1 x x 3 6 3 2
1 x x 3 x 3 2
А как правильно:
1 4 5 3 6 3 2
1 4 5 x 6 3 2
1 4 5 x x 3 2
1 4 x x x 3 2
1 x x x x 3 2
1 x x x x x 2
Добавлю в статью вместо спорного примера. Спасибо большое.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Динамика по подотрезкам: базовые вещи и «одна хорошо, а две лучше»