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

К>>Для каждого цветка (#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)
S>Разве min(Q[j,m]) не будет при m=0?

Так мы же перебираем по j, а не по m. Для текущего i и каждого m найдём минимум по j.

Если думать вслух, как Винни-пух:
Допустим, я стою у пятого бочонка с мёдом.
Если бы я ничего не съел (m=0), я бы потратил 0 минут.
Если бы я съел один (m=1)... это мог быть нулевой, первый, ... четвёртый бочонок. И я бы выбрал тот, который открывается раньше всех.
Если бы я съел два (m=2)... Это значит, что я съел два, заканчивая нулевым (ой, такое невозможно), или два, заканчивая первым (Q[1,2]), или два, заканчивая вторым (Q[2,2]), или третьим (Q[3,2]), или четвёртым (Q[4,2]).
Если бы я съел три (m=3)... Я бы выбирал между Q[2,3], Q[3,3], Q[4,3]
...
Наконец, если бы я съел все четыре, то это было бы, без вариантов, Q[4,4].

Во всех этих случаях, я получу наилучшее время Q[5,0] (воздержусь от съедения на этот раз, отложу на потом), Q[5,1], ..., Q[5,5].


Кстати, да, я немного напутал в рекуррентной формуле.
T[i,m] = min(Q[j,m] | j<i) — на подходе в состоянии "съедено m" выбираем кратчайший вариант

Q[i,m] = min(Q_skip[i,m], Q_take[i,m]) — на выходе в состоянии "съедено m" выбираем — это мы воздержались или съели в этот раз
Q_skip[i,m] = T[i,m] — воздержались — это значит, с чем пришли, с тем ушли, и не потратили времени
Q_take[i,m] = max(T[i,m-1], t[i]) + d — поели — это значит, пришли чуть голодными (m-1), при необходимости дождались нужного момента, и потратили порцию времени.


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

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

Время на забег туда-обратно, разумеется. Мы же, когда вычитали t[i] := t[i]-x[i]*v, должны были заначить время на забег: x[z]*v*2.


Мой алгоритм, очевидно, квадратичный.
Можно ли его сделать логлинейным, — интересный вопрос.