Решение задачи #36. Python Яндекс CodeRun, Распил брусьев

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Распил брусьев.
Сложность: Средняя.
Статус решения: "Решено".

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

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

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

Формат ввода:
Первая строка входных данных содержит целое число LL (2≤L≤1062≤L≤106) — длину бруса и целое число NN (1≤N≤1001≤N≤100) — количество распилов. Во второй строке записано NN целых чисел СiСi​ (0<Ci<L0<Ci​<L) в строго возрастающем порядке — места, в которых нужно сделать распилы.

Формат вывода:
Выведите одно натуральное число — минимальную стоимость распила.

Решение:

Python

import sys

def main():
    """
    Решает задачу о минимальной стоимости распила бруса.

    Args:
        None

    Returns:
        None
    """

    # Считываем входные данные: l - длина бруса, n - количество распилов
    l, n = map(int, sys.stdin.readline().split())
    # Считываем места распилов
    c = list(map(int, sys.stdin.readline().split()))

    # Добавляем 0 и L в список точек распила для удобства обработки граничных случаев
    c = [0] + c + [l]
    n += 2 # Увеличиваем n, так как добавили 2 точки

    # Создаем таблицу dp для динамического программирования
    # dp[i][j] - минимальная стоимость распила бруса от c[i] до c[j]
    dp = [[0] * n for _ in range(n)]

    # Заполняем таблицу dp, используя рекуррентную формулу
    for length in range(2, n): # Перебираем длину отрезка (минимум 2, так как нужен хотя бы один распил)
        for i in range(n - length): # Перебираем начальную точку отрезка
            j = i + length # Конечная точка отрезка
            dp[i][j] = float('inf') # Инициализируем минимальную стоимость бесконечностью
            for k in range(i + 1, j): # Перебираем точку последнего распила на текущем отрезке
                # cost - стоимость распила отрезка [i, j] с последним распилом в точке k
                # cost = стоимость распила [i, k] + стоимость распила [k, j] + стоимость текущего распила (длина отрезка [i, j])
                cost = dp[i][k] + dp[k][j] + (c[j] - c[i])
                # Обновляем минимальную стоимость для отрезка [i, j]
                dp[i][j] = min(dp[i][j], cost)

    # Выводим результат: dp[0][n-1] - минимальная стоимость распила всего бруса (от 0 до L)
    print(dp[0][n - 1])

if __name__ == "__main__":
    main()

Объяснение кода

Динамическое программирование:
Задача решается с помощью динамического программирования. Ключевая идея заключается в том, чтобы разбить исходную задачу на подзадачи меньшего размера и сохранить результаты их решения в таблице dp.

Предварительная обработка:
Для удобства обработки граничных случаев (начало и конец бруса) в список точек распила c добавляются 0 и L (длина бруса).

Таблица dp:
Создается двумерная таблица dp, где dp[i][j] хранит минимальную стоимость распила отрезка бруса между точками c[i] и c[j].

Рекуррентная формула:
Основная логика заключается в рекуррентной формуле:
dp[i][j] = min(dp[i][k] + dp[k][j] + (c[j] - c[i])) для всех k от i+1 до j-1.

dp[i][k] - минимальная стоимость распила отрезка от c[i] до c[k].
dp[k][j] - минимальная стоимость распила отрезка от c[k] до c[j].
(c[j] - c[i]) - стоимость текущего распила, равная длине отрезка.
Заполнение таблицы: Таблица dp заполняется итеративно, начиная с отрезков длиной 2 и постепенно увеличивая длину. Для каждого отрезка [i, j] перебираются все возможные точки последнего распила k и выбирается минимальная стоимость.

Результат:
Результат хранится в dp[0][n-1], что соответствует минимальной стоимости распила всего бруса от 0 до L.

Оптимизация:
Данное решение использует динамическое программирование, что позволяет избежать пересчета одних и тех же подзадач многократно. Временная сложность алгоритма O(N^3), где N - количество распилов. Это приемлемо для заданных ограничений (N ≤ 100).

Источник решения: hdhai.com