TCIRC
解題紀錄

d086. Q-6-18. 矩陣乘法鏈 - TCFSH CIRC Judge

AP325-d086-2.cpp

// Author : ysh
// 07/21/2022 Thu 16:31:59.31
// https://judge.tcirc.tw/ShowProblem?problemid=d086
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    vector<int>f(n + 1);
    for(int &i : f) {
        cin>>i;
    }
    vector<vector<int>>mark(n + 2,vector<int>(n + 2,LONG_LONG_MAX));
    for(int i = 0;i<=n;i++) {
        mark[i][i] = 0;
        mark[i][i + 1] = 0;
    }
    for(int i = 1;i<=n;i++) {
        for(int j = 0;i + j<=n;j++) {
            for(int k = j;k < i + j;k++) {
                //cerr<<j<<" "<<j + i<<" "<<k<<"\n";
                if(mark[j][k] == LONG_LONG_MAX || mark[k][j + i] == LONG_LONG_MAX) continue;
                mark[j][j + i] = min(mark[j][j + i],mark[j][k] + mark[k][j + i] + (f[j] * f[k] * f[j + i]));
                // for(auto i : mark) {
                //     for(auto j : i) {
                //         cout<<j<<" ";
                //     }
                //     cout<<"\n";
                // }
                // cout<<"\n";
            }
        }
    }
    cout<<mark[0][n];
    return 0;
}