[c++] 백준 11049 행렬 곱셈 순서

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

11049번: 행렬 곱셈 순서

11066번과 풀이법은 똑같고, 점화식만 조금 바꾸면 AC받을 수 있다.

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

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
pair<int,int> matrix[555];
int dp[555][555];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin>>n;
    for(int i=1; i<=n; i++){
        int r,c; cin>>r>>c;
        matrix[i] = {r,c};
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n-i; j++){
            int tmp=987654321;
            for(int k=j; k<i+j; k++){
                int cost = matrix[j].F*matrix[k].S*matrix[j+i].S;
                tmp = min(tmp,dp[j][k]+dp[k+1][i+j] + cost);
            }
            dp[j][i+j] = tmp;
        }
    }
    cout << dp[1][n];
    return 0;
}