Разбор добавил Генадий Врублёвский

Сначала отсортируем гвоздики по возрастанию координат. Решим следующую подзадачу: 
найдем минимальную длину веревочек, необходимую для того, чтобы связать первые k гвоздиков согласно условию (обозначим требующуюся для этого длину веревочек ak).

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

Научимся вычислять ak. Заметим, что в оптимальной конфигурации (для первых k гвоздиков) между последним 
 (k-м) и предпоследним ((k-1)-м) гвоздиками ниточка есть всегда, а вот между предпоследним ((k-1)-м)  
и предпредпоследним ((k-2)-м) она может либо быть, либо не быть. В первом случае первые k-1 гвоздиков 
 удовлетворяют условию задачи, во втором - первые k-2. Значит ak=min(ak-1,ak-2)+lk-1,k, где lk-1,k - расстояние между k-м и k-1-м гвоздиками (в отсортированном массиве). 
 Для удобства вычислений удобно ввести фиктивные первый и нулевой элементы равные 0 и бесконечности соответственно  
(в реальной программе в роли бесконечности обычно выступает какое-нибудь достаточно большое число, например для данной задачи вполне подойдет 30000). 
Теперь последовательно заполняя массив a с помощью данной формулы, мы получим верный ответ на поставленную задачу в элементе aN. 


Число действий, выполненных данным алгоритмом, пропорционально N.

Отредактировал(а) Антон Евдокимов