прикреплённый файл:pegsNropes.py к странице LecturesVMSH/2012-03-28

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 В дощечке в один ряд вбиты гвоздики. Любые два гвоздика можно соединить
   5 ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы
   6 к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех
   7 ниточек была минимальна.
   8 Ввод: X-координаты гвоздиков
   9 '''
  10 
  11 # Сначала отсортируем гвоздики по возрастанию координат. Решим следующую подзадачу: 
  12 # найдем минимальную длину веревочек, необходимую для того, чтобы связать
  13 # первые k гвоздиков согласно условию (обозначим требующуюся для этого длину
  14 # веревочек ak).
  15 
  16 # Можно считать, что любая ниточка связывает два соседних гвоздика (иначе ее
  17 # можно разрезать на несколько частей, связывающих все гвоздики между теми,
  18 # которые связывала наша ниточка изначально).
  19 
  20 # Научимся вычислять ak. Заметим, что в оптимальной конфигурации (для первых
  21 # k гвоздиков) между последним (k-м) и предпоследним ((k-1)-м) гвоздиками
  22 # ниточка есть всегда, а вот между предпоследним ((k-1)-м) и предпредпоследним
  23 # ((k-2)-м) она может либо быть, либо не быть. В первом случае первые k-1
  24 # гвоздиков удовлетворяют условию задачи, во втором - первые k-2. Значит
  25 # ak=min(ak-1,ak-2)+l(k-1,k), где l(k-1,k) - расстояние между k-м и k-1-м
  26 # гвоздиками (в отсортированном массиве).
  27 
  28 Nails=sorted([int(n) for n in raw_input().split()])
  29 N=len(Nails)
  30 
  31 Links=[0]+[Nails[i]-Nails[i-1] for i in xrange(1,N)]
  32 Ropes=[0,Links[1],Links[1]+Links[2],Links[1]+Links[3]]+[0]*(N-4)
  33 for i in xrange(4,N):
  34     Ropes[i]=min(Ropes[i-1],Ropes[i-2])+Links[i]
  35 print Ropes[-1]