Вывод в задаче о золотой горе

Question

Работаю над задачей по динамическому программированию.

Задача старая и из олимпиады: На рисунке изображен треугольник из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающемся на основании треугольника.

Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо. Количество строк и сам треугольник задаются с помощью текстового файла

Собственно код самой задачи у меня уже есть. Однако мне ещё нужно сделать вывод этого треугольника и отметить элементы этого треугольника по которым шла программа(либо цветом либо ещё как-то).

**7**
**3** 8
**8** 1 0
2 **7** 4 4
4 **5** 2 6 5

Каким образом мне выделить именно те элементы которые мне нужны, я понятия не имею. Поэтому прошу помощи. Заранее спасибо. Вот собственно код:

#include<iostream>

#include "fstream"
using namespace std;
int main()
{
    int** a, N, i, j, ** b;
    ifstream file("1.txt");
    file >> N;
    cout << N << endl;
    a = new int* [N];
    b = new int* [N];
    for (i = 0; i < N; i++)
    {
        a[i] = new int[N];
        b[i] = new int[N];
        for (j = 0; j <= i; j++)
            b[i][j] = 0;
    }
    for (i = 0; i < N; i++)
        for (j = 0; j <= i; j++)
            file >> a[i][j];
    b[0][0] = a[0][0];
    for (i = 0; i < N - 1; i++)
        for (j = 0; j <= i; j++)
        {
            if (b[i + 1][j] < b[i][j] + a[i + 1][j]) {
                b[i + 1][j] = b[i][j] + a[i + 1][j];
                cout << a[i + 1][j] << endl;
            }
            if (b[i + 1][j + 1] < b[i][j] + a[i + 1][j + 1])
                b[i + 1][j + 1] = b[i][j] + a[i + 1][j + 1];
        }
    int max = b[N - 1][0];
    for (i = 1; i < N; i++)
        if (b[N - 1][i] > max)
            max = b[N - 1][i];
    for (i = 0; i < N - 1; i++)
        for (j = 0; j <= i; j++)
        {
            cout << a[i][j] << " ";
        }
    cout << "Max summ= " << max << endl;
    return 0;
}

Answer 1

Например, так:

Заведите ещё один массив. Когда в if происходит обновление ячейки b[][], записывайте в соотв. ячейку c[][], откуда пришли - из левой или из правой верхней ячейки.

Когда работа закончена, с нижней строчки от максимума разматывайте до верха цепочку.

Для начала нужно найти индекс максимума

int imax = 0;
for (i = 1; i < N; i++)
    if (b[N - 1][i] > b[N - 1][imax])
        imax = i;

Затем пройти по записанной в c[][] последовательности

for (i = n-1; i > 0; i--) {
    a[i][imax] = - a[i][imax]; //пометили число минусом
    imax = c[i][imax];
}

Теперь осуществляем вывод по строкам в нормальном порядке, но если число отрицательное, выводим звёздочку, -a[i][imax], звёздочку

Как вариант не портить a

for (i = n-1; i > 0; i--) {
    t = imax;
    imax = c[i][imax];
    c[i][t] = -1; //пометили ячейку, при выводе проверяем c на это значение
}

БЛОГ НА HUSL

Вывод в задаче о золотой горе

Ответы (1 шт):