Multiplication Puzzle

din.cpp

#include<fstream>
#include<math.h>

using namespace std;

const int MAX_SIZE = 100;
const int MAX_INT = 9999999;

int a[MAX_SIZE];
int d[MAX_SIZE][MAX_SIZE]; // Вот здесь хранятся частичные решения. Размерности означают следующее:
// d[a][b] = наилучшее решение для отрезка от элемента с номером a до b
int n = 0;

int main(int argc, char *argv[])
{
    ifstream fi("input.txt");
    ofstream fo("output.txt");
    
    fi >> n;
    
    for (int i = 0; i < n; i++)
        fi >> a[i];

/* 
тут то, что я тебе рассказывал делается не сверху вниз, а низу вверх
сначала решаем для маленьких кусочков, потом для все более и более 
длинных
*/      
    for (int m = 3; m <= n; m++) // вот это длина кусочка
        for (int k = 0; k <= n - m; k++) // ну а тут мы перебираем все кусочки этой длины k - индекс первого 
//элемента текущего кусочка
        {
            int l = k + m - 1; // индекс последнего элемента текущего кусочка(длины m)
            
            d[k][l] = MAX_INT; // ну это чтобы потом минимум искать

            // а здесь на основании уже решенных подзадач для меньших(на 1) кусочков составлялем решение для
// кусочка текущей длины
            for (int i = k + 1; i <= l; i++) //а именно, i = индекс элемента, на котором делим. напомню: k - 
//индекс 1го элемента отрезка, l - индекс последнего. Формула лучше выражается кодом чем словами - смотри
                d[k][l] = min(d[k][l], d[k][i] + d[i][l] + a[i]*a[l]*a[k]);    
        }
        
    fo << d[0][n - 1];
    
    fi.close();
    fo.close();
    return 0;
}