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

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

К>А вот динамическое программирование тут появляется...

Вообще в полном алгоритме я предполагал обычную рекурсию: мы выбираем элементы, способные дать максимум цветов, затем повторяем поиск для подмножества (t'') из всех элементов справа от выбранного элемента (k), из времени которых вычли время этого элемента:
t''[i] = t'[i+k] — t[k], 0<i<=N-k

К>Для каждого цветка (#i) на прямом пути найдём
К>- минимальное время подхода к нему T[i,m] при котором черепаха успела съесть 0<=m<=i цветов
К>- соответственно, минимальное время ухода от него
К>- — если черепаха не ела этот цветок, Q[i,m] = T[i,m]
К>- — если осталась и съела, Q[i,m+1] = max(T[i,m],t[i]) + d

К>Для нулевого цветка, понятное дело, T[0,0] = 0.
К>Для всех последующих, T[i,m] = min(Q[j,m] | 0<=j<i)
Разве min(Q[j,m]) не будет при m=0?

К>Для последнего цветка # z=n-1 потратим время на обратный ход:
К>R[m] = Q[z,m] + d * (z-m)

R[m] = Q[z,m] + d * (z-m) + Q[z,0]
Если не ошибаюсь — надо учесть и время ходьбы

К>Наилучшее время — это min(R[m] | 0<=m<n)

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

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

К>А вот динамическое программирование тут появляется...

Вообще в полном алгоритме я предполагал обычную рекурсию: мы выбираем элементы, способные дать максимум цветов, затем повторяем поиск для подмножества (t'') из всех элементов справа от выбранного элемента (k), из времени которых вычли время этого элемента:
t''[i] = t'[i+k] — t[k], 0<i<=N-k

К>Для каждого цветка (#i) на прямом пути найдём
К>- минимальное время подхода к нему T[i,m] при котором черепаха успела съесть 0<=m<=i цветов
К>- соответственно, минимальное время ухода от него
К>- — если черепаха не ела этот цветок, Q[i,m] = T[i,m]
К>- — если осталась и съела, Q[i,m+1] = max(T[i,m],t[i]) + d

К>Для нулевого цветка, понятное дело, T[0,0] = 0.
К>Для всех последующих, T[i,m] = min(Q[j,m] | 0<=j<i)
Разве min(Q[j,m]) не будет при m=0?

К>Для последнего цветка # z=n-1 потратим время на обратный ход:
К>R[m] = Q[z,m] + d * (z-m)

R[m] = Q[z,m] + d * (z-m) + Q[z,0]
Если не ошибаюсь — надо учесть и время обратного хода, а не только поедание цветов.

К>Наилучшее время — это min(R[m] | 0<=m<n)