競プロ初中級者100問

ALDS1 10B 連鎖行列積

この記事で使うアルゴリズム

動的計画法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B&lang=ja

この問題は動的計画法を用いて解くことができます。

方針

dp[i][j]を考えます。このリストは行列積M_i, M_i+1,..., M_jを計算するコストを表します。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
INF = 10**10
N = int(input())
dp = [[INF]*N for _ in range(N)]
R = []
for n in range(N):
    r, c = map(int,input().split())
    R.append(r)
R.append(c)

for i in range(N):
    dp[i][i] = 0 # 対角成分すなわち、行列積Miを計算するコストは0である

for l in range(1,N): # iとjの差分
    for i in range(N-l):
        j = i+l    
        for k in range(i,j):
            # cost(左側行列積) + cost(右側行列積) + 行列計算のコスト
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+R[i]*R[k+1]*R[j+1]) # 初回はR[0]*R[1]*R[2]
print (dp[0][-1])

具体的な計算例

行列積M_2 M_3 M_4 M_5をM_2 M_3とM_4 M_5の行列積として求める際の具体的な計算は以下のようになります。

1
2
3
4
5
6
7
8
9
R: R2  R3  R4  R5  R6
M:  (M2  M3)(M4  M5)

l=1
i=2
j=5
k=3

M[2][5] = min(M[2][5], M[2][3] + M[4][5] + R[2]*R[4]*R[6])

記事情報

  • 投稿日：2020年5月15日
  • 最終更新日：2020年5月15日