Courses

動的プログラミング

一次元ダイナミクス

Module: 一次元ダイナミクス

Problem

5 /7

チケットの購入

Problem

N 人の列が新しいミュージカルの初演のチケットを求めて並んでおり、各人が 1 枚のチケットを購入したいと考えています。キュー全体に対して1つのチケット売り場しか機能しなかったため、チケットの販売は非常に遅く、「ゲスト」を連れてきました。必死に列を作る。最も賢い人は、通常、レジ係が片手で複数のチケットを販売する方が、同じチケットを 1 枚ずつ販売する場合よりも速く売れることにすぐに気付きました。

したがって、彼らは、何人か立っている人が最初の人にお金を渡して、全員のチケットを購入することを提案しました.

しかし、投機家と戦うために、レジ係は 1 人 3 枚までしかチケットを販売できなかったので、この方法で合意に達することができるのは連続して 2 人か 3 人だけでした。

レジ係が i 番目の人に 1 枚のチケットを売るのに Ai 秒を費やし、B_i 2 枚のチケットを販売するのに数秒、3 枚のチケット - C_i 秒。すべての顧客にサービスを提供できる最小時間を計算するプログラムを作成してください。

団結した人々のグループのチケットは、常に最初のグループが購入することに注意してください。また、スピードを上げるために余分なチケット (つまり、誰も必要としないチケット) を購入する人もいません。

入力:
- 最初の行には数値 N が含まれます - キュー内のバイヤーの数 (\(1<=N<=5000\)) ;
- 次は N 個の自然数の三重 A_i, B_i , C_i. これらの番号はそれぞれ 3600 を超えません。列に並んでいる人は、レジ係から順番に番号が付けられます。

出力: 単一の数値を出力 - すべての顧客にサービスを提供できる最小時間 (秒単位)。