\begin{proposal}{Horses}{horses.in}{horses.out}{}

\Author

Антон Ковшаров

\ProblemIdea
      
Есть прямая, на ней n городов с 1 по n через 1 км. Нужно добраться с первого до n. Каждому городу сопоставлено число - в какой момент времени оттуда отходит автобус(лошадь), который первый километр проезжает за одну минуту, второй за две и так далее, так как перегревается(устает). Нужно доехать до конца как можно скорее, из всех возможных с наименьшим количеством пересаживания(покупки новых лошадей). Ты успеваешь взять лошадь если она отходит в момент времени t а ты прибыл в тот город в момент времени T <= t. 

\SolutionIdea

Динамика dp[i][k] - минимальное время за которое можем добрать до i-го города, используя ровно k - лошадей. 
Переберем сколько минимально лошадей нам достаточно, чтобы успеть на лошадь в этом городе. Возьмем лошадь здесь и переберем сколько на ней проедем - прорелаксируем впереди. 

\ProblemVariations


\ProblemComplexity                              

За квадрат


\WrongSolutions


\end{proposal}
