Задача
Имеется прямоугольная таблица размером 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 целых чисел (каждое из которых не превышает по модулю 106) - значения клеток таблицы.
Известно, что искомое количество путей с максимальной суммой не превышает 109.
Выходные данные
Вывести два целых числа - максимальную сумму и количество путей.
Пример
Входные данные
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Выходные данные
42 1
Объяснение
Сначала рассмотрим задачу поиска просто максимальной суммы (без
количества путей). Серию подзадач поставим как “Какую максимальную
сумму e(i, j) можно насобирать, дойдя из 1-й строки до j-й клеточки i-й
строки?”. Номер клеточки в 1-й строке (откуда начинать путь) не задаётся
как параметр. Целевая задача не принадлежит серии, но, зная решение
(M, j)-подзадач при всех j, остаётся лишь найти максимум в одномерном
массиве. Решениями тривиальных (1, j)-подзадач при всех j будут просто
e(1, j) = a(1, j) (для каждой клеточки 1-й строки есть ровно один допустимый путь — состоящий только из этой клеточки). Решения нетривиальных
задач будут строиться по уравнению ДП:
e(i, j) = max {e(i−1, j−1), e(i−1, j), e(i−1, j+1)} + a(i, j) (10)
(с поправкой, что при j = 1 пропускается первый из вариантов, а при
j = N — последний). Для доказательства преобразуем формулу к виду
e(i, j)= max{e(i−1, j−1) + a(i, j), e(i−1, j) + a(i, j), e(i−1, j+1) + a(i, j)}.
Первый из вариантов даёт максимально возможную сумму среди всех
путей, приходящих в (i, j) через левого верхнего соседа, второй —
среди путей через верхнего соседа, и третий — среди путей через
правого верхнего. Максимум из них и будет оптимальным решением для
клеточки (i, j).
Теперь перейдём к поиску количества q(i, j) путей с максимальной
суммой, приводящих в клеточку (i, j). Для любой клеточки 1-й строки
q(1, j)=1 — путь только один, он и есть максимальный. Разные пути с одинаковой максимальной суммой возникают, когда два или три варианта, из
которых выбирается max в (10), имеют одинаковые максимальные значения. В таком случае надо сложить количества путей с максимальной
суммой всех максимальных направлений.
Решение без подсчета количества путей.
#include
using namespace std;
int main()
{
int n, m, maxx;
cin >> n >> m;
int** arr = new int* [n];
for (int i = 1; i <= n; i++) { arr[i] = new int[m]; }
int brr[210][210];
for (int i = 1; i <= n; i++)
{
brr[i][0] = brr[i][m + 1] = -2000000000;
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
for (int i = 1; i <= n; i++) {
brr[1][i] = arr[1][i];
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= m; j++) {
brr[i][j] = max(max(brr[i - 1][j - 1], brr[i - 1][j]), brr[i - 1][j + 1]) + arr[i][j];
}
}
maxx = brr[n][1];
for (int i = 2; i <= m; i++){
if (brr[n][i] > maxx) {
maxx = brr[n][i];
}
}
cout << maxx;
}
Не могу понять как подсчитать количество путей, помогите , пожалуйста. Заранее спасибо!
