No.39 シルクロード (Silk Road)


時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

現在カザフスタンがある地域には,古くは「シルクロード」と呼ばれる交易路があった.

シルクロード上には N + 1 個の都市があり,西から順に都市 0, 都市 1, ... , 都市 N と番号がつけられている.都市 i - 1 と都市 i の間の距離 (1 ≦ i ≦ N) は Di である.

貿易商である JOI 君は,都市 0 から出発して,都市を順番に経由し,都市 N まで絹を運ぶことになった.都市 0 から都市 N まで M 日以内に移動しなければならない.JOI 君は,それぞれの日の行動として,以下の 2 つのうちいずれか 1 つを選ぶ.

  • 移動: 現在の都市から 1 つ東の都市へ 1 日かけて移動する.現在都市 i - 1 (1 ≦ i ≦ N) にいる場合は,都市 i に移動する.
  • 待機: 移動を行わず,現在いる都市で 1 日待機する.

移動は大変であり,移動するたびに疲労度が溜まっていく.シルクロードでは日毎に天候の変動があり,天候が悪い日ほど移動には苦労を要する.

JOI 君が絹を運ぶのに使える M 日間のうち j 日目 (1 ≦ j ≦ M) の天候の悪さは Cj であることが分かっている.都市 i - 1 から都市 i (1 ≦ i ≦ N) に j 日目 (1 ≦ j ≦ M) に移動する場合,疲労度が Di × Cj だけ溜まってしまう.移動を行わず待機している日は疲労度は溜まらない.

JOI 君は,それぞれの日の行動をうまく選ぶことで,できるだけ疲労度を溜めずに移動したい.JOI 君が M 日以内に都市 N に移動するときの,移動を開始してから終了するまでに溜まる疲労度の合計の最小値を求めよ.

入力

入力は 1 + N + M 行からなる.

1 行目には,2 つの整数 N, M (1 ≦ N ≦ M ≦ 1000) が空白を区切りとして書かれている.これは,シルクロードが N + 1 個の都市からなり,JOI 君が絹を都市 0 から都市 N まで M 日以内に運ばなければならないことを表す.

続く N 行のうちの i 行目 (1 ≦ i ≦ N) には,整数 Di (1 ≦ Di ≦ 1000) が書かれている.これは,都市 i - 1 と都市 i の間の距離が Di であることを表す.

続く M 行のうちの j 行目 (1 ≦ j ≦ M) には,整数 Cj (1 ≦ Cj ≦ 1000) が書かれている.これは,j 日目の天候の悪さが Cj であることを表す.

出力

JOI 君が M 日以内に都市 N に移動するときの,移動を開始してから終了するまでに溜まる疲労度の合計の最小値を 1 行で出力せよ.

入出力例

入力1

3 5
10
25
15
50
30
15
40
30

出力1

1125

入出力例 1 において,溜まる疲労度の合計を最小にするように JOI 君が移動するには次のようにする.

  • 1 日目は待機する.
  • 2 日目に都市 0 から都市 1 へ移動する.このとき溜まる疲労度は 10 × 30 = 300 である.
  • 3 日目に都市 1 から都市 2 へ移動する.このとき溜まる疲労度は 25 × 15 = 375 である.
  • 4 日目は待機する.
  • 5 日目に都市 2 から都市 3 へ移動する.このとき溜まる疲労度は 15 × 30 = 450 である.

JOI 君がこのように移動した場合に溜まる疲労度の合計は 300 + 375 + 450 = 1125 である.これが最小値である.

入力2

2 6
99
20
490
612
515
131
931
1000

出力2

31589





解説


単純な解法として,JOI 君の移動方法をすべて試して疲労度の合計を最小にするものを探すといったものが考えられる.しかし,JOI 君は最大で M 日間使えることを考えると,待機する日の選び方は M 日の中から M - N 日を選ぶ方法程度はあると言える.このような選ぶ組み合わせの数は M, N が大きくなるに従って爆発的に増大してしまうので,この単純な解法では時間内に大きな入力データに対して答えを得ることは難しい.

そこで重要なのは,JOI 君が都市 i にいて,それまでに j 回の行動をした (j 日間が経過した) 状態について,そこから先の移動方法を考えるにあたってそれ以前の移動方法は関係ないという事実である.「JOI 君が j 日間かけて都市 i に至るときに溜まる疲労度の合計の最小値」を f(i, j) とすれば,求める答えは f(N, N), f(N, N+1), ..., f(N, M) のうちの最小値となる.

f(i, j) を求める方法を考えよう.JOI 君が最後にとった行動について考えると以下のようになる.

  • JOI 君が最後に「移動」をしていた場合,前日に JOI 君は都市 i - 1 におり,この移動で疲労度が Di × Cj だけ溜まる.
  • JOI 君が最後に「待機」をしていた場合,前日にも JOI 君は都市 i におり,疲労度の合計は変化していない.

ゆえに,f(i, j) は f(i - 1, j - 1) + Di × Cj (JOI 君が最後に「移動」をしていた場合) と f(i, j - 1) (JOI 君が最後に「待機」をしていた場合) のうち小さい方である.ただし,初日に関しては前日の行動が存在しないので f(0, 0) = 0 と決められる.

これより,f(0, 0) が決まっていて,それ以外の f(i, j) の値は f(i - 1, j) と f(i - 1, j - 1) の値から決まることがわかるので,i の小さい方から f(i, j) の値を順に求めていくことが可能である.(i, j) の値は約 M × N 通り (厳密にはもう少し小さい) あり,ひとつの f(i, j) の計算は 2 通りの値を見るだけでよいから,全体で M × N に比例する時間で f の値をすべて計算することが可能である.この手法を用いれば,すべての入力データに対して高速に答えを得ることができる.

上に用いた手法のように,より小さい問題 (この場合は日数や都市数が小さい問題) の答えから,より大きい問題の答えを順に計算していく手法は一般に動的計画法と呼ばれている.情報オリンピックでは過去にも動的計画法を用いる問題を出題しているので,さまざまなタイプの動的計画法を知るために過去の問題やその解説を参照するのもよいだろう.