5854. Максимальная сумма базовая

Имеется прямоугольная таблица размером n строк на m столбцов. В каждой клетке записано целое число. По ней можно пройти сверху вниз, начиная из любой клетки верхней строки, дальше каждый раз переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (i, j) можно перейти или на (i + 1, j – 1), или на (i + 1, j), или на (i + 1, j + 1); в случае j = m последний из трёх описанных вариантов становится невозможным, а в случае j = 1 – первый) и закончить маршрут в какой-нибудь клетке нижней строки.

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

Вход. В первой строке записаны n и m (1 ≤ n, m ≤ 200) – количество строк и столбцов. Дальше в каждой из следующих n строк записано m целых чисел (не превышающих по модулю 10⁶) – значения клеток таблицы.

Выход. Вывести единственное число – найденную максимальную сумму.

Пример входа	Пример выхода
4 3 1 15 2 9 7 5 9 2 4 6 9 -1	42

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть a[i][j] – исходная таблица. Пусть dp[i][j] хранит максимальную сумму чисел на пути с любой клетки первой строки до клетки (i, j). Тогда

dp[i][j] = max(dp[i – 1][j – 1], dp[i – 1][j], dp[i – 1][j + 1]) + a[i][j]

Для корректного вычисления значений первого и последнего столбца следует положить dp[i][0] = dp[i][m + 1] = -∞.

Первую строку массива dp проинициализируем значениями первой строки таблицы а: dp[1][i] = a[1][i], 1 ≤ i ≤ m.

Ответом на задачу будет максимальное число в последней (n-ой) строке таблицы dp.

Пример

Рассмотрим входной тест.

Реализация алгоритма

Объявим константу – минимум MIN, а также массивы a и dp.

#define MAX 202

#define MIN -2000000000

int a[MAX][MAX], dp[MAX][MAX];

Читаем входные данные. Верхний левый угол входной таблицы храним в a[1][1]. Столбцы с номерами 0 и m + 1 в массиве dp заполним минимально возможным числом MIN.

scanf("%d %d", &n, &m);

for (i = 1; i <= n; i++)

{

dp[i][0] = dp[i][m + 1] = MIN;

for (j = 1; j <= m; j++)

scanf("%d", &a[i][j]);

}

Первую строку массив а скопируем в массив dp.

for (i = 1; i <= n; i++)

dp[1][i] = a[1][i];

Пересчитываем максимальные суммы на путях от верхней строки до клетки (i, j) в массиве dp.

for (i = 2; i <= n; i++)

for (j = 1; j <= m; j++)

dp[i][j] = max(max(dp[i - 1][j - 1], dp[i - 1][j]),

dp[i - 1][j + 1]) + a[i][j];

Находим наибольшее число в последней (n-ой) строке.

res = MIN;

for (i = 1; i <= m; i++)

if (dp[n][i] > res) res = dp[n][i];

Выводим ответ.

printf("%d\n", res);

Java реализация

import java.util.*;

public class Main

{

static int a[][], dp[][];

final static int MIN = -2000000000;

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m = con.nextInt();

dp = new int[n+1][m+2];

a = new int[n+1][m+2];

for (int i = 1; i <= n; i++)

{

dp[i][0] = dp[i][m + 1] = MIN;

for (int j = 1; j <= m; j++)

a[i][j] = con.nextInt();;

}

for (int i = 1; i <= m; i++)

dp[1][i] = a[1][i];

for (int i = 2; i <= n; i++)

for (int j = 1; j <= m; j++)

dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + a[i][j];

int res = MIN;

for (int i = 1; i <= m; i++)

if (dp[n][i] > res) res = dp[n][i];

System.out.println(res);

con.close();

}

}