Description:
24:00までに配達できなかったら、荷物1つ、1分あたり1$を支払いますという顧客との約束なのに、今24:00です。
円状の道路上に初期の自分の位置と配達ポイントが並んでいて、各々の位置と、そこに届けなくてはならない荷物の数が与えられた時、最低でもいくら支払う羽目になるか。
点の数は300以下で、答えは10億以下。
Answer:
DPでもメモ付き探索でも解けるが、メモ付き探索が楽だろう。
最適な配達を行っている最中では、配達し終えた範囲は連続していて、新しく一ヶ所配達を終えた時には右端か左端にいると考えて問題ないので、
テーブルは、配達し終えた範囲の右端 * 配達し終えた範囲の左端 * (今の位置:右or左) で、300x300x2となる。
テーブルには、残った荷物、今からの時間に対して払わなくてはならない金額を入れて置く。
Source: