Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Somescout, Вы писали:

S>>1) Вычтем из всех моментов времени время подхода черепахи:
S>>t'[i] = t[i]-(x[i]/Vmax)-f(i)*d — f(i) число съеденых цветов на промежутке от 0 до i-1

К>Опередил!

S>>2) Очевидно, что для каждого t'[i], максимальное количество цветов = (T2-t'[i])/d , сортируем по этому ключу по убыванию => S.

К>Э, не понял.
Черепахе нужно минимум время d чтобы съесть цветок, T2 — это из предыдущего алгоритма время оставщееся после выбора очевидных вариантов, соответственно T2-(время ожидания цветения этого цветка)/(время поедания цветка) — сколько цветков черепаха сможет съесть максимум, если будет ожидать раскрытия этого цветка.

Fix: T2 = T1 = t[N]-x[N]/Vmax, т.к. всё же есть конфигурации когда выбор цветов с 0 временем ожидания менее выгоден.

К>Ну и к тому же, сортировка по убыванию (T2-t'[i])/d = (T2/d)-t'[i]/d — это сортировка по возрастанию t'[i]
В принципе да, значит сортировать достаточно отсортировать t' по возрастанию


S>>3) Рекурсивно находим максимальное число цветов, которое мы можем съесть на прямом пути при выбраном элементе k из S. Если оно равно (T'-t'[i])/d — то нашли, если меньше — запоминаем максимум и переходим к следующему элементу. Когда максимум будет больше либо равен (T'-t'[i])/d мы нашли решение.

К>Нет ли здесь претензии на всё тот же полный перебор?
В худшем случае да, но ведь мы проходим по убыванию максимально возможного числа съеденых цветов, соответственно в процессе практический max(съеденых) должен стать равным теоретическому, вот тут мы и прервёмся