DevJourney · code I wrote while learning

main.cpp

1.1 KB
#include <iostream>
using namespace std;

const long long INF = (1LL << 62);

void printOrder(int s[100][100], int i, int j)
{
    if (i == j)
    {
        cout << "A" << i;
        return;
    }

    cout << "(";
    printOrder(s, i, s[i][j]);
    cout << ",";
    printOrder(s, s[i][j] + 1, j);
    cout << ")";
}

int main()
{
    int n;

    if (!(cin >> n))
        return 0;

    long long p[101];

    for (int i = 0; i <= n; i++)
        cin >> p[i];

    long long m[100][100];
    int s[100][100];

    for (int i = 1; i <= n; i++)
        m[i][i] = 0;

    for (int len = 2; len <= n; len++)
    {
        for (int i = 1; i <= n - len + 1; i++)
        {
            int j = i + len - 1;
            m[i][j] = INF;

            for (int k = i; k < j; k++)
            {
                long long q =
                    m[i][k] +
                    m[k + 1][j] +
                    p[i - 1] * p[k] * p[j];

                if (q < m[i][j])
                {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }

    cout << m[1][n] << endl;

    printOrder(s, 1, n);
    cout << endl;

    return 0;
}