Python

Задача на python

Евгений — логист, и у него есть n товаров. За продажу i-го товара компания получит ai монет прибыли (она может быть и отрицательной). В стране, в которой живет Евгений, странные правила выбора товаров для доставки: Евгений может выбрать любой отрезок товаров, но только один, и доставить все товары на этом отрезке (отрезком называется непрерывная последовательность товаров). Для доставки нужны грузовики, в каждый из которых помещается не более k любых товаров, причем за использование каждого грузовика нужно заплатить s монет. Найдите, какое максимальное количество монет может получить Евгений, учитывая затраты на грузовики.

Формат ввода

Первая строка содержит три целых числа n, k и s (1≤n≤105,1≤k≤10,1≤s≤109) — количество товаров, а также числа k и s.
Вторая строка содержит n целых чисел a1,a2,…,an (−109≤ai≤109) — стоимости товаров.

Формат вывода

Выведите одно число — максимальное количество монет, которое может получить Евгений

Пример 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 монет на один грузовик.
Во втором примере оптимально выбрать любой отрезок из двух товаров.

В третьем примере не получится доставить ни одного товара так, чтобы получить прибыль.

В четвертом примере оптимально будет выбрать отрезок от второго товара до восьмого.
Александр Гуляев
Александр Гуляев
190
Это - задача дня.

Решается слегка модифицированным алгоритмом Джея Кадане.
 p, k, s = (int(t) for t in input().split())

a = list(int(t) for t in input().split())



max_profit = 0

maxp = [0] * k

for i in range(k - 1):

    m = min(k, i + 1)

    maxp = [max(maxp[-1] + a[i], 0) - s] + [max(maxp[i - 1] + a[i], -s) for j in range(1, m)] + [0] * (k - m)

for i in range(k - 1, p):

    maxp = [max(maxp[-1] + a[i], 0) - s] + [max(maxp[j - 1] + a[i], -s) for j in range(1, k)]

    max_profit = max(*maxp, max_profit)



print(max_profit)

Сложность алгоритма O(p * k), при малых k - можно считать, что линейная. При p=9999, k=3 на onlinegdb отрабатывает за 0.25 с, при k=250 - балансирует на грани секунды. Это включая время на запуск программы.


P.S. Ты первый, кто по-человечески изложил условие этой задачи в вопросе. Предшественники кидались кусками кода непонятного назначения с просьбой его "ускорить". :-) Поэтому лайк за вопрос.
Алексей Малышев
Алексей Малышев
87 571
Лучший ответ
Александр Гуляев И да, пожалуйста.
Виктор Мухин знаешь как исправить ошибку runtime error?
Если вы собираетесь перевезти свой настольный компьютер, мышь, клавиатуру, веб-камеру и монитор, у вас есть несколько вариантов:

Вынуть жесткий диск: Если вы вынете жесткий диск из компьютера, то с собой у вас останутся только данные, хранящиеся на этом диске, такие как ваша операционная система Windows 10, программы и файлы. Вы сможете вставить этот жесткий диск в другой компьютер, и если ваша операционная система и настройки были правильно настроены на этом диске, то они также будут доступны на новом компьютере. Однако, может потребоваться перенастройка драйверов и настроек для нового оборудования.

Перенос компьютера вместе с корпусом: Если ваш настольный компьютер не слишком громоздкий и у вас есть возможность перевезти его вместе с корпусом, то это может быть более удобным вариантом. Вы сможете сохранить все настройки, программы и данные на компьютере таким образом. Однако, стоит учитывать, что перевозка компьютера может быть сложной и рискованной процедурой, особенно при авиаперелете, так как компьютерное оборудование может подвергаться вибрациям и ударам во время транспортировки.

Перенос данных на другие носители: Если вы не можете взять с собой свой компьютер или жесткий диск, вы можете скопировать важные данные на другие носители, такие как флеш-накопители, внешние жесткие диски или облачные хранилища. Вы сможете восстановить эти данные на другом компьютере или устройстве после переезда и использовать их на новом компьютере.

Не забудьте также о возможных ограничениях и правилах транспортировки компьютерного оборудования в аэропорту или в других местах, где вы планируете перевозку. При необходимости, проконсультируйтесь с перевозчиками или авиалиниями, чтобы узнать о требованиях и рекомендациях по перевозке компьютерной техники.
АШ
Анатолий Шулепов
293
Александр Гуляев Мне решение надо..

Похожие вопросы