7K12 blog

猫でも分かるアルゴリズム解説

AOJ ALDS1_10_B Matrix Chain Multiplication

f:id:tkr987:20200713222229p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4663385

  • 行列の順番は変えずに「どの区間の行列から掛け算するのが最善か」という問題
  • 初期値は rep(i, 0, n) dp[i][i] = 0; それ以外は inf
  • 繰り返しは rep(range, 1, n) rep(l, 0, n)
  • 更新は rep(m, l, r) dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + nyaa[l] * nyaa[m+1] * nyaa[r+1]);
  • 出力は dp[0][n-1]
  • 区間DPの二重ループは range から書かないと答えが出ない

f:id:tkr987:20200713224815p:plain
行列サイズ (p0, p1) と (p1, p2) の積は p0 × p1 × p2 だけ演算回数が必要。不思議なことに、どのグループから掛け算するかで演算回数が変化する(行列の順番は変えてはいけない)。

行列 M_iの行サイズを P_i、列サイズを P_{i+1}とする(列サイズのインデックスが1ずれることに注意)。閉区間で連続した2グループの行列積を考えると [l, m]×[m+1, r] となるので(l, m, r は p のインデックスに対応)、行列積は区間DPを使って以下のように計算する。

rep(m, l, r) dp[l][r] = min(dp[l][r], dp[l][m] + dp[m+1][r] + nyaa[l] * nyaa[m+1] * nyaa[r+1]);