[Baekjoon] 11049. 行列乗算順[G 3]

📚 質問する

https://www.acmicpc.net/problem/11049

📖 に答える

列は500個まで並ぶことができる.
全ての順番を確認すると499!もう出てきたので、時間内には無理です.
そこで、dpを利用して、メモを作ります.注記を使用して2 Dマトリクスを作成します.
入力された行列は順次読み込まれ、i~jの乗算回数の最大値はdp[i][j]に記憶される.
iとjの差は小さい値から充填されます.
ABCDを作る場合を考えてみると、A*(BCD) (AB)*(CD) (ABC)*D3つの思考に分けることができます.
それぞれ2つの束に分けることができます.二つに分けて、前の組み合わせはXで、後ろの組み合わせはYです.
1つ目はX = A、Y = BCD、2つ目はX = AB、Y = CDである.
したがって、最終的に得られる値は次のとおりです.
これはすべてのX,YにおけるX 만드는 최소값 + Y 만드는 최소값 + X의 시작값 * X의 끝값(Y의 시작값) * Y의 끝값の最小値である.
5x33x22x66x45x3030901183x2036722x60486x40
以上のように得ることができる.

📒 コード#コード#

def recur(a, b):
    if dp[a][b] != -1:
        return dp[a][b]
    
    ret = 2 ** 31
    for i in range(a, b):
        ret = min(ret, recur(a, i) + recur(i + 1, b) + arr[a][0] * arr[i][1] * arr[b][1])
    dp[a][b] = ret
    return ret

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1] * n for _ in range(n)]   # [a, b] 까지 중 곱셈 연산 횟수의 최솟값
for i in range(n):  # [i, i]는 행렬이 하나이므로 0이다.
    dp[i][i] = 0
print(recur(0, n - 1))

🔍 結果