Livedoorブログからの移動
はてなブログからの移動

Mr. Rito Post Office | Aizu Online Judge

解き方

  • z_{i-1}からz_iへの行き方は次の2通り
    • 陸路で行く
    • 船のあるところまで陸路で行き、船で適当なところまで行き、再度陸路
  • 前計算として、陸路での最短距離、海路での最短距離をWarshall Floydで求めておく
  • dp[i][j] = 船がjにある状態でz_iまで集配するための最短距離として動的計画法
    • dp[0][z_0] = 0、その他INFが初期状態
    • [tex:O(RN2)]は間に合うか怪しいと思ったが、間に合った

ハマったところ

  • Warshall Floydまでは思いついたが、直前の船の位置だけメモ化すればよいことに気づかず、しばらくO(R^N)の解法しか思いつかなかった

github.com