この質問 (最後の質問) は、Benelux Algorithm Programming Contest-2007 に掲載されました。
http://www.cs.duke.edu/courses/cps149s/spring08/problems/bapc07/allprobs.pdf
問題文の要約:
企業は、利益を最大化するために、特定の入力に対していつ購入するか、販売するか、または何もしないかの戦略を立てる必要があります。入力は次の形式です。
6
4 4 2
2 9 3
....
....
これは、入力が 6 日間与えられることを意味します。
1 日目: 4 株を取得します。それぞれの価格は 4 ドルで、最大で 2 株を売却できます
。2 日目: 2 株を取得し、それぞれの価格は 9 ドルで、最大で 3 株を売却でき
ます
達成できる最大の利益を出す必要があります。
この問題をどうしようか考え中です。力ずくでやると時間がかかりすぎる気がします。これを 0-1 ナップサックのような DP の問題に変換できるとしたら? いくつかの助けをいただければ幸いです。