Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо…
1
Обозначим через $max[i][j]$ и $min[i][j]$ соответственно максимальную и минимальную суммы монет на пути из левой верхней клетки в клетку $(i,j)$.
2
Если в клетку можно прийти сверху или слева, выбираем лучший и худший из соответствующих вариантов и прибавляем монету в текущей клетке.$$max[i][j] = a[i][j] + \max(max[i-1][j], max[i][j-1])$$
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Исполнитель Робот начинает движение из левой верхней клетки и может перемещаться…
1
Из электронной таблицы считываются достоинства монет и расположение внутренних стен.
2
Для каждой клетки вычисляется максимальная сумма монет на допустимом пути из левой верхней клетки. Переходы выполняются только вправо и вниз и только через проходы без стен.$$D_{\max}(i,j)=a_{i,j}+\max\limits_{(k,l)\to(i,j)}D_{\max}(k,l)$$
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и за один шаг может переместиться…
1
Для максимальных сумм последовательно заполняем таблицу: в каждой клетке прибавляем её значение к большему из значений сверху и слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
2
В правой нижней клетке максимальная сумма равна $38$.
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо…
1
Обозначим через $M_{i,j}$ максимальную, а через $m_{i,j}$ минимальную сумму, которую можно получить при попадании в клетку $(i,j)$.$$M_{1,1}=m_{1,1}=a_{1,1}$$
2
Для каждой клетки рассматриваем только переходы из клетки сверху и из клетки слева, если между ними нет стены.$$M_{i,j}=a_{i,j}+\max M_{p,q},\qquad m_{i,j}=a_{i,j}+\min m_{p,q}$$
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
1
Создадим для каждой клетки два значения: максимальную и минимальную сумму монет на пути из левой верхней клетки в эту клетку.$$maxSum[i,j],\ minSum[i,j]$$
2
Начальная клетка получает значение своей монеты. В каждую доступную соседнюю клетку можно перейти только вправо или вниз, если между клетками нет стены.$$maxSum[i,j] = a[i,j] + \max(maxSum\text{ предшественников})$$