N х N square is divided into cells. There is a natural number in each cell. The Robot performer can move through
N х N square is divided into cells. There is a natural number in each cell. The Robot performer can move through the cells by performing one of three operations: 1. Move one cell to the right. 2. Move one cell upwards. 3. Move diagonally one cell to the right and upwards. In the case of a move of type 1 or 2, the sum accumulated by the Robot increases by the number in the cell it moves to. In the case of a move of type 3, the sum accumulated by the Robot increases by twice the number in the cell it moves to. At the beginning, the Robot is in the bottom left cell and is assigned
Максик 14
задание состоит в определении максимальной суммы, которую может набрать Робот при перемещении вверх вправо к верхней правой ячейке.Для нахождения решения мы можем использовать динамическое программирование. Для каждой ячейки (i, j) мы будем хранить максимальную сумму, которую Робот может набрать, доходя до этой ячейки. Для ячейки (1, 1) максимальная сумма будет равна значению этой ячейки.
Далее, мы будем заполнять все остальные ячейки по очереди, начиная с левой нижней ячейки и двигаясь вправо и вверх. Для каждой ячейки (i, j) мы будем выбирать наибольшую сумму из трех возможных вариантов перемещения Робота:
1. Из ячейки (i-1, j) перемещение по вертикали вверх.
2. Из ячейки (i, j-1) перемещение по горизонтали вправо.
3. Из ячейки (i-1, j-1) перемещение по диагонали вверх и вправо.
Мы будем прибавлять двойное значение ячейки (i-1, j-1) к максимальной сумме для перемещения по диагонали и обычное значение для прочих перемещений.
Наконец, когда мы достигнем верхней правой ячейки (N, N), максимальная сумма, которую может набрать Робот, будет находиться в этой ячейке.
Давайте рассмотрим пример:
Представим, что у нас есть квадрат 3x3 со следующими значениями:
\[
\begin{array}{ccc}
3 & 1 & 5 \\
2 & 9 & 7 \\
6 & 4 & 8 \\
\end{array}
\]
Мы начнем с заполнения первой строки и первого столбца:
\[
\begin{array}{ccc}
3 & 4 & 9 \\
5 & & \\
11 & & \\
\end{array}
\]
Затем мы заполняем оставшиеся ячейки:
\[
\begin{array}{ccc}
3 & 4 & 9 \\
5 & 13 & 16 \\
11 & 17 & 25 \\
\end{array}
\]
Таким образом, максимальная сумма, которую Робот может набрать в данном случае, равна 25.
Можно заметить, что при использовании динамического программирования мы эффективно избегаем повторного вычисления одних и тех же значений, что делает алгоритм эффективным и быстрым.
Таким образом, ответ на задачу состоит в нахождении максимальной суммы, которую Робот может набрать при перемещении из нижнего левого угла в верхний правый угол квадрата. Мы используем динамическое программирование для заполнения ячеек с максимальной суммой и находим максимальную сумму в верхней правой ячейке.