Вот вопрос:
Раму был ленивым фермером. Он унаследовал от отца довольно большую ферму и хороший дом. Раму сдал ферму в аренду другим и получил довольно приличный доход. Его отец держал дома буйвола и продавал его молоко, но буйвол умер через несколько дней после отца.
Раму тоже хотел заработать на буйволах, но совсем другим способом. Он решил, что его будущее заключается в спекуляции на буйволах. На рынке в его деревне каждый день покупали и продавали буйволов. Цена колебалась в течение года, но в любой отдельный день цена всегда была одной и той же.
Он решил, что будет покупать буйволов, когда цена будет низкой, и продавать их, когда цена будет высокой, и в процессе накапливать большое богатство. К сожалению, в его доме было место только для одного буйвола, поэтому он мог владеть не более чем одним буйволом в любое время.
Прежде чем выйти на рынок буйволов, он решил изучить колебания цен на буйволов за последние несколько дней и определите максимальную прибыль, которую он мог бы получить. Предположим, цена буйвола за последние 10 дней колебалась как10 12 8 11 11 10 12 15 13 10
Раму — ленивый парень, и он подсчитал, что за последние 10 дней он был бы готов посетить рынок не более 5 раз (каждый раз, чтобы купить или продать буйвола). При этом максимальная прибыль, которую он мог бы получить, составляет 9 рупий. Для этого он покупает буйвола в 1-й день, продает его во 2-й день, покупает еще одного в 3-й день и продает его в 8-й день. мог бы заработать больше денег. Он мог купить в 1-й день, продать во 2-й день, купить в 3-й день, продать в 4-й день, купить в 6-й день и продать в 8-й день, чтобы получить прибыль в размере 10 рупий.
Ваша задача - помочь Раму рассчитать максимальная сумма, которую он может заработать, спекулируя на буйволах, с учетом истории ежедневных цен на буйволов за период и ограничения на то, сколько раз Раму готов выйти на рынок в течение этого периода.Формат ввода
Первая строка ввода содержит два целых числа N и K, где N — количество дней, за которые доступны данные о ценах, а K — максимальное количество раз, которое Раму готов посетить рынок крупного рогатого скота. . Следующие N строк (строка 2, 3,...,N+1) содержат по одному натуральному числу в каждой. Целое число в строке i+1, 1 ≤ i ≤ N, указывает цену буйвола в день i.Выходной формат
Одно неотрицательное целое число, указывающее максимальную сумму прибыли, которую может получить Раму, если он совершит не более K поездок на рынок.
Можно предположить, что N ≤ 400 и K ≤ 400.< br/> Лимит времени = 3сек.
Если бы у нас не было ограничения k, мы могли бы решить эту проблему, используя жадный подход,
while c < N
i = c
while price[day i] > price[day i+1] increment i;
j = i+1
while price[day j] < price[day j+1] increment j;
add price[day j] - price[day i] to out profit
c = j+1
Но мы не можем использовать его здесь, потому что посетить в определенный день или нет, зависит от того, сколько дней мы посетили. Вот что я пробовал
//Store all the pairs generated in the previous algorithm in a linked list L, each
//element has two attributes buy,sell
while length of L > k/2
find an element i in the list such the (L[i].sell- L[i-1].buy) -
(L[i-1].buy - L[i-1].sell) - (L[i].buy - L[i].sell) is maximized.
Then set L[i-1].sell to L[i].sell and delete i from the list
Это проблема онлайн-судьи, и когда я представил ее, у меня было превышено ограничение по времени для некоторых тестовых случаев и неправильный ответ для некоторых и правильный только для одного тестового примера.
Что не так в моем методе и почему он может быть медленным, потому что он занимает около O(NK) времени, где N и K ‹ 400.
Как я могу улучшить свой алгоритм, чтобы решить задачу правильно?
EDIT: это не домашнее задание, я нашел эту проблему здесь: http://opc.iarcs.org.in/index.php/problems/BUFFALOES
