質問は次のとおりです。
ラムは怠惰な農夫でした。彼は父親からかなり大きな農場と素敵な家を受け継いでいた。ラムは農地を他人に貸し出し、それなりの収入を得ていた。彼の父親はバッファローを家で飼ってミルクを売っていましたが、バッファローは父親がそうした数日後に亡くなりました。
ラムも水牛からいくらかのお金を稼ぎたいと思っていましたが、それはまったく別の方法でした. 彼は自分の将来は水牛についての投機にあると判断した. 彼の村の市場では、水牛が毎日売買されていました。価格は年間を通じて変動しますが、どの日でも価格は常に同じです。
彼は、水牛を安い時に買い、高い時に売り、莫大な富を蓄えることにした。残念なことに、彼の家には水牛が 1 頭しか入らなかったので、一度に所有できる水牛は 1 頭まででした。
彼は水牛市場に参入する前に、過去数日間の水牛の価格の変動を調査し、彼が得ることができた最大の利益を決定することにしました. 過去 10 日間の水牛の価格が次のように変化したとします。10 12 8 11 11 10 12 15 13 10
Ramu は怠け者で、過去 10 日間で最大 5 回 (毎回水牛を売買するために) 市場に行くつもりだったと考えています。これを考えると、彼が得ることができた最大の利益は 9 ルピーです。これを達成するために、彼は 1 日目にバッファローを購入し、2 日目に販売し、3 日目にもう 1 つ購入して 8 日目に販売します。もっと稼げたかもしれない。彼は 1 日目に買って、2 日目に売って、3 日目に買って、4 日目に売って、6 日目に買って、8 日目に売って、10 ルピーの利益を得ることができたはずです。
あなたの仕事は、ある期間の毎日の水牛の価格の履歴と、この期間中にラムが市場に行く回数の制限を考慮して、ラムが水牛で投機することによって得ることができる最大額を計算するのを助けることです.入力形式 入力
の最初の行には、2 つの整数 N と K が含まれます。ここで、N は価格データが利用可能な日数であり、K は Ramu が牛市場を訪問する最大回数です。次の N 行 (行 2、3、...、N+1) には、それぞれ 1 つの正の整数が含まれます。行 i+1 の整数、1 ≤ i ≤ N は、i 日の水牛の価格を示します。出力形式
Ramu が最大で K 回の市場への移動を行った場合に、Ramu が得ることができる最大利益額を示す 1 つの非負の整数。
N ≤ 400 かつ K ≤ 400 と仮定しても構いません。
制限時間 = 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
これはオンライン審査員の問題で、私がそれを提出したとき、一部のテスト ケースで制限時間を超過し、一部のテスト ケースで間違った答えを受け取り、1 つのテスト ケースだけを修正しました。
N と K < 400 の場合、O(NK) 時間かかるため、どのように遅くなる可能性があり
ますか? 問題を正しく解決するためにアルゴリズムを改善するにはどうすればよいですか?
編集: これは宿題ではありません。ここでこの問題を見つけました: http://opc.iarcs.org.in/index.php/problems/BUFFALOES