прикреплённый файл:2013-03-22.raspil.py к странице LecturesVMSH/Python/2013-03-22

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 Решить задачу «Распил брусьев». Вам нужно распилить деревянный брус на несколько кусков в заданных местах. Распилочная компания берет k рублей за распил одного бруска длиной k метров на две части в любом месте. Определите минимальную стоимость распила бруса на заданные части.
   5 
   6     Формат входных данных. Первая строка входных данных содержит целое число L (2≤L≤10**6) - длину бруса и целое число N (1≤N≤100) - количество распилов. Во второй строке записано N целых чисел Сi (0<Ci<L) в строго возрастающем порядке - места, в которых нужно сделать распилы.
   7 
   8     Формат выходных данных. Выведите одно натуральное число - минимальную стоимость распила.
   9 '''
  10 
  11 import sys
  12 
  13 if len(sys.argv)>1:
  14     # генератор
  15     import random
  16     def summand(M,n):
  17         '''Представить M в виде n случайных слагаемых'''
  18         # Сгенерируем случайную линейку
  19         L=[random.random() for i in xrange(n)]
  20         ret=[]
  21         for i in xrange(n):
  22             # длина оставшейся линейки
  23             s=sum(L)
  24             # отделим от оставшегося M очередную долю
  25             ret.append(int(round(M*L.pop()/s)))
  26             # Уменьшим M
  27             M-=ret[-1]
  28         return ret
  29 
  30     N=sys.argv[1] and sys.argv[1].isdigit() and int(sys.argv[1]) or random.randint(50,100)
  31     L=len(sys.argv)>2 and int(sys.argv[2]) or random.randint(800000,1000000)
  32     R=[0]
  33     while 0 in R:
  34         R=summand(L,N+1)
  35     #print >> sys.stderr, R
  36     for i in xrange(1,N+1): R[i]+=R[i-1]
  37     print L, N
  38     print " ".join(map(str,R[:N]))
  39     sys.exit(0)
  40 
  41 def check():
  42     # NB: введением кеширования эта функция превращаетcя в решение!
  43     def rasp(i,j):
  44         """Решить задачу для подбревна между i-й и j-й пометкой"""
  45         return j-i>1 and R[j]-R[i]+min(rasp(i,k)+rasp(k,j) for k in xrange(i+1,j)) or 0
  46     R=[0]+Log[:]+[L]
  47     return rasp(0,N+1)
  48 
  49 def get_half():
  50     "Неправильное решение, предполагающее, что пилить надо всегда ближе к середине"
  51     def rasp(i,j):
  52         if j-i<2: return 0
  53         k=min(xrange(i+1,j), key=lambda k: abs(R[j]+R[i]-2*R[k]))
  54         return R[j]-R[i]+rasp(i,k)+rasp(k,j)
  55     R=[0]+Log[:]+[L]
  56     return rasp(0,N+1)
  57     # 19 20 [3, 5, 6] [3, 2, 1, 4]
  58 
  59 def solve():
  60     "Решение методом динамического программирования"
  61     # Добавим фиктивные распилы в начале и в конце
  62     R=[0]+Log[:]+[L]
  63     # Стоимисть минимального распила подбревна между i-м и j-м распилом
  64     Rasp=[[0]*(N+2) for i in xrange(N+2)]
  65     for d in xrange(2,N+2):
  66         for i in xrange(N+2-d):
  67             Rasp[i][i+d]=R[i+d]-R[i]+min(Rasp[i][k]+Rasp[k][i+d] for k in xrange(i+1,i+d))
  68     return Rasp[0][N+1]
  69         
  70 
  71 L,N=map(int,raw_input().split())
  72 Log=map(int,raw_input().split())
  73 
  74 c,c2=solve(),solve()
  75 if c!=c2:
  76     print c,c2,Log,[Log[0]]+[Log[i+1]-Log[i] for i in xrange(N-1)]+[L-Log[-1]]
  77     sys.exit(1)
  78 else:
  79     print c