Решение задачи Распил брусьев с Яндекс Контест

Без пояснения   Просмотров: 5532

Вам нужно распилить деревянный брус на несколько кусков в заданных местах. Распилочная компания берет K рублей за распил одного бруска длиной K метров на две части.

Понятно, что различные способы распила приводят к различной суммарной стоимости заказа. Например, рассмотрим брус длиной 10 метров, который нужно распилить на расстоянии 2, 4 и 7 м, считая от одного конца. Это можно сделать несколькими способами. Можно распилить сначала на отметке 2 м, потом 4 и, наконец, 7 м. Это приведет к стоимости 10+8+6=24, потому что сначала длина бруса, который пилили, была 10 м, затем она стала 8 м, и, наконец, 6 м. А можно распилить иначе: сначала на отметке 4 м, затем 2, затем 7м. Это приведет к стоимости 10+4+6=20, что лучше.

Определите минимальную стоимость распила бруса на заданные части.

Код 

import math

l, n = map(int, input().split())
d = []
a = list(map(int, input().split()))
a.insert(0, 0)
a.append(l)
n += 2
for i in range(n):
    d.append([0] * n)
for j in range(1, n):
    for i in range(j - 2, -1, -1):
        d[i][j] = math.inf
        for k in range(i + 1, j):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        d[i][j] += a[j] - a[i]
print(d[0][n - 1])

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp