Cherchez vol 2 - Evaluare Optimala - pag 180

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

void afisare(int i, int j, vector < vector < int > >& dp, vector < int >& a) {
    if(i == dp[j][i])
        cout << a[i];
    else {
        cout << "(";
        afisare(i, dp[j][i], dp, a);
        cout << ")";
    }
    cout << "o";
    if(j == dp[j][i] + 1)
        cout << a[j];
    else {
        cout << "(";
        afisare(dp[j][i] + 1, j, dp, a);
        cout << ")";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector < int > a(N + 1);
    for(int i = 1; i <= M; ++i)
        cin >> a[i];
    vector < vector < int > > op(N + 1, vector < int >(N + 1));
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            cin >> op[i][j];
    vector < vector < int > > cost(N + 1, vector < int >(N + 1));
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            cin >> cost[i][j];
    vector < vector < int > > dp(M + 1, vector < int >(M + 1)),
                              rez(M + 1, vector < int >(M + 1));
    for(int i = 1; i <= M; ++i)
        rez[i][i] = a[i];
    for(int lg = 2; lg <= M; ++lg)
        for(int i = 1; i <= M - lg + 1; ++i) {
            int j = i + lg - 1, mn = INF, kmin;
            for(int k = i; k < j; ++k)
                if(mn > dp[i][k] + dp[k + 1][j] + cost[rez[i][k]][rez[k + 1][j]]) {
                    mn = dp[i][k] + dp[k + 1][j] + cost[rez[i][k]][rez[k + 1][j]];
                    kmin = k;
                }
            dp[i][j] = mn;
            dp[j][i] = kmin;
            rez[i][j] = op[rez[i][kmin]][rez[kmin + 1][j]];
        }
    cout << dp[1][M] << '\n';
    afisare(1, M, dp, a);
}