[an error occurred while processing the directive]

    <p class=header>Задача 02-2. &quot;Гвоздики&quot;<br><i>(Разбор)</i></p>
<p>Сначала отсортируем гвоздики по возрастанию координат. 
Решим следующую подзадачу: найдем минимальную длину веревочек, необходимую 
для того, чтобы связать первые k гвоздиков согласно условию  
(обозначим требующуюся для этого длину веревочек a<sub>k</sub>). </p>

<p>Можно считать, что любая ниточка связывает 
два соседних гвоздика (иначе ее можно разрезать на несколько частей,
 связывающих 
все гвоздики между теми, которые связывала наша ниточка изначально). 

<p>
Научимся вычислять a<sub>k</sub>. Заметим, что 
в оптимальной конфигурации (для первых k гвоздиков) между последним (k-м) и 
предпоследним ((k-1)-м) гвоздиками ниточка есть всегда, а вот между
 предпоследним ((k-1)-м)
и предпредпоследним ((k-2)-м)
она может либо быть, либо не быть. В первом случае 
первые k-1 гвоздиков удовлетворяют условию задачи, во втором - первые k-2. 
Значит 
a<sub>k</sub>=min(a<sub>k-1</sub>,a<sub>k-2</sub>)+l<sub>k-1,k</sub>, 
где l<sub>k-1,k</sub> - расстояние между k-м и k-1-м гвоздиками
 (в отсортированном массиве). Для удобства вычислений удобно ввести фиктивные 
первый и нулевой элементы равные 0 и бесконечности соответственно 
(в реальной программе в роли бесконечности обычно выступает какое-нибудь 
достаточно большое число, например для данной задачи вполне подойдет 30000).
Теперь последовательно заполняя массив a с помощью данной формулы, мы получим 
верный ответ на поставленную задачу в элементе a<sub>N</sub>.</p>
<p>Число действий, выполненных данным алгоритмом, пропорционально N.</p>
    [an error occurred while processing the directive]