Задача: Доставка
Евгений — логист, и у него есть n товаров. За продажу i-го товара компания получит ai монет прибыли (она может быть и отрицательной). В стране, в которой живет Евгений, странные правила выбора товаров для доставки: Евгений может выбрать любой отрезок товаров, но только один, и доставить все товары на этом отрезке (отрезком называется непрерывная последовательность товаров). Для доставки нужны грузовики, в каждый из которых помещается не более k любых товаров, причем за использование каждого грузовика нужно заплатить s монет. Найдите, какое максимальное количество монет может получить Евгений, учитывая затраты на грузовики.
Формат ввода
Первая строка содержит три целых числа n, k и s (1≤n≤10^5,1≤k≤10,1≤s≤10^9) — количество товаров, а также числа k и s.
Вторая строка содержит n целых чисел a1,a2,…,an (−10^9≤ai≤10^9) — стоимости товаров.
Формат вывода
Выведите одно число — максимальное количество монет, которое может получить Евгений
Пример 1
Ввод:
6 3 10
0 -4 16 -7 3 8
Вывод:
6
Пример 2
Ввод:
3 2 10
9 9 9
Вывод:
8
Пример 3
Ввод:
5 3 15
3 2 4 5 1
Вывод:
0
Пример 4
Ввод:
10 3 5
-3 9 7 15 -10 9 7 6 -1 0
Вывод:
28
Примечания
В первом примере оптимально будет выбрать только товар со стоимостью 16 и потратить 10 монет на один грузовик.
Во втором примере оптимально выбрать любой отрезок из двух товаров.
В третьем примере не получится доставить ни одного товара так, чтобы получить прибыль.
В четвертом примере оптимально будет выбрать отрезок от второго товара до восьмого.
1 ответ
@olegustinov69 Для решения этой задачи можно использовать алгоритм динамического программирования. Мы будем поддерживать две переменные: max_profit, которая будет хранить максимальную прибыль, и current_profit, которая будет хранить текущую прибыль на текущем отрезке. Мы также будем поддерживать счетчик current_length, который будет хранить текущую длину отрезка.
Мы будем проходить по всем товарам в порядке их расположения и обновлять значения current_profit и current_length. Если current_profit становится отрицательным, то это означает, что текущий отрезок не приносит прибыли, и мы сбрасываем его до 0 и сбрасываем current_length до 0. Если current_length становится больше k (максимального количества товаров, которое можно поместить в грузовик), то мы начинаем сдвигаться вправо, сбрасывая current_profit и current_length до 0 на каждом шаге.
После обработки всех товаров, мы сравниваем current_profit с max_profit и обновляем max_profit, если current_profit больше. Затем мы выводим значение max_profit, которое будет являться максимальной прибылью, которую можно получить Евгению.
Вот реализация данного алгоритма на языке Python:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
def max_profit(n, k, s, a): max_profit = 0 current_profit = 0 current_length = 0 for i in range(n): current_profit += a[i] current_length += 1 if current_profit < 0: current_profit = 0 current_length = 0 if current_length > k: current_profit -= a[i - k] current_length -= 1 max_profit = max(max_profit, current_profit - (current_length * s)) return max_profit # Ввод данных n, k, s = map(int, input().split()) a = list(map(int, input().split())) # Вызов функции и вывод результата print(max_profit(n, k, s, a)) |