[Baekjoon] 11049. 行列乗算順[G 3]
6442 ワード
📚 質問する
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))🔍 結果
Reference
この問題について([Baekjoon] 11049. 行列乗算順[G 3]), 我々は、より多くの情報をここで見つけました https://velog.io/@yunhlim/Baekjoon-11049.-행렬-곱셈-순서-G3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol