Тапсырма 18 ЕГЭ по информатикаға: ФИПИ шешімдері қадамдық жауаптарымен

Составим таблицу максимальных сумм. В каждой клетке прибавляем её значение к большему из результатов для верхней и левой клеток.$$M_{4,4}=6+\max(M_{3,4},M_{4,3})=6+\max(26,35)=41$$

Составим таблицу минимальных сумм. В каждой клетке прибавляем её значение к меньшему из результатов для верхней и левой клеток.$$m_{4,4}=6+\min(m_{3,4},m_{4,3})=6+\min(16,28)=22$$

Заполняем таблицу максимальных сумм. В каждой клетке прибавляем стоимость монеты к большему из значений сверху и слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$

Для правой нижней клетки максимальная сумма получается равной $41$.$$M_{4,4}=41$$

Сначала считываем из файла стоимость монет в каждой клетке и наличие стен между соседними клетками.

Для каждой клетки храним два значения: максимальную и минимальную сумму, которую можно получить при попадании в эту клетку из левой верхней клетки.

Обозначим через $max[i][j]$ и $min[i][j]$ соответственно максимальную и минимальную суммы монет на пути из левой верхней клетки в клетку $(i,j)$.

Если в клетку можно прийти сверху или слева, выбираем лучший и худший из соответствующих вариантов и прибавляем монету в текущей клетке.$$max[i][j] = a[i][j] + \max(max[i-1][j], max[i][j-1])$$

Составим таблицу максимальных сумм. В каждую клетку добавляем её номинал к большему из значений сверху и слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$

Кесте максимальных сумм имеет вид:$$\begin{matrix}1&9&17&21\\11&10&18&24\\12&15&30&32\\14&18&35&41\end{matrix}$$

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

Для клетки с бонусом $a_{i,j}$ рассматриваем переходы из верхней и левой клеток. Переход через стену не учитываем.$$min_{i,j}=a_{i,j}+\min\limits_{(k,l)\to(i,j)} min_{k,l},\quad max_{i,j}=a_{i,j}+\max\limits_{(k,l)\to(i,j)} max_{k,l}$$

Робот начинает в левой верхней клетке и забирает монету из неё. Для каждой последующей клетки рассматриваем только переходы слева и сверху, если между клетками нет стены.$$M_{i,j}^{\max}=a_{i,j}+\max(M_{i-1,j}^{\max},M_{i,j-1}^{\max})$$

Аналогично вычисляем минимальную возможную сумму для каждой клетки.$$M_{i,j}^{\min}=a_{i,j}+\min(M_{i-1,j}^{\min},M_{i,j-1}^{\min})$$

Из электронной таблицы считываются достоинства монет и расположение внутренних стен.

Для каждой клетки вычисляется максимальная сумма монет на допустимом пути из левой верхней клетки. Переходы выполняются только вправо и вниз и только через проходы без стен.$$D_{\max}(i,j)=a_{i,j}+\max\limits_{(k,l)\to(i,j)}D_{\max}(k,l)$$

Робот движется только вправо и вниз, поэтому в клетку он может попасть только из клетки сверху или из клетки слева.

Для каждой клетки строим два значения: минимальную и максимальную сумму бонусов на пути из левой верхней клетки в эту клетку.

Поскольку Робот движется только вправо и вниз, в каждую клетку он может прийти только сверху или слева. Для максимальной суммы выбираем большее из возможных значений, для минимальной — меньшее.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1}),\quad m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$

Для максимальных сумм получаем последнюю строку таблицы: $14, 17, 35, 41$. Следовательно, максимальная сумма равна $41$.$$M_{4,4}=41$$

Для максимальных сумм последовательно заполняем таблицу: в каждой клетке прибавляем её значение к большему из значений сверху и слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$

В правой нижней клетке максимальная сумма равна $38$.

Считаем значение каждой клетки электронной таблицы равным стоимости монеты в этой клетке. Для каждой клетки храним два значения: максимальную и минимальную сумму, с которой Робот может в неё попасть.

Для клетки, в которую можно попасть сверху, переход выполняется из клетки над ней; для клетки, в которую можно попасть слева, — из клетки слева. Если проход через соответствующую стену запрещён, этот переход не рассматривается.

Введём для каждой клетки две величины: максимальную и минимальную сумму монет, которую можно собрать при попадании в эту клетку.

Для клетки без стены значения вычисляются по формулам: к максимуму из допустимых соседей сверху и слева прибавляется стоимость монеты в клетке; аналогично вычисляется минимум.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1}),\quad m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$

Каждый маршрут из левой верхней клетки в правую нижнюю содержит одну и ту же последовательность перемещений: $N-1$ перемещений вправо и $N-1$ перемещений вниз. Для каждой клетки вычислим максимальную и минимальную сумму монет на пути из…

В первую клетку записываем её стоимость. В первой строке и первом столбце значения накапливаются единственным возможным способом.

Обозначим через $M_{i,j}$ максимальную, а через $m_{i,j}$ минимальную сумму, которую можно получить при попадании в клетку $(i,j)$.$$M_{1,1}=m_{1,1}=a_{1,1}$$

Для каждой клетки рассматриваем только переходы из клетки сверху и из клетки слева, если между ними нет стены.$$M_{i,j}=a_{i,j}+\max M_{p,q},\qquad m_{i,j}=a_{i,j}+\min m_{p,q}$$

Разобьём задачу на подзадачи: для каждой клетки найдём минимальную и максимальную сумму бонусов, которую можно получить при попадании в эту клетку.

В начальной клетке обе величины равны её бонусу. Для каждой следующей клетки рассматриваем только те клетки сверху и слева, с которыми нет стены.

Считаем стоимость монеты в каждой клетке и сведения о стенах из приложенной электронной таблицы.

Для каждой клетки вычисляем две величины: максимальную и минимальную сумму, которую можно набрать при попадании в эту клетку. Переходы выполняются только вправо и вниз и только через проходы без стен.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$

Для каждой клетки создаются два значения: максимальная и минимальная суммы монет на пути из начальной клетки в данную клетку.

Если в клетку можно попасть из клетки слева, соответствующее значение получают добавлением монеты текущей клетки к значению в левой клетке.

Робот движется только вправо и вниз, поэтому значения для клетки можно вычислять после обработки клетки сверху и клетки слева.

Для каждой клетки строятся две динамические таблицы: $min[i][j]$ — минимальная сумма бонусов, а $max[i][j]$ — максимальная сумма бонусов на допустимом пути из начальной клетки.

Создадим для каждой клетки два значения: максимальную и минимальную сумму монет на пути из левой верхней клетки в эту клетку.$$maxSum[i,j],\ minSum[i,j]$$

Начальная клетка получает значение своей монеты. В каждую доступную соседнюю клетку можно перейти только вправо или вниз, если между клетками нет стены.$$maxSum[i,j] = a[i,j] + \max(maxSum\text{ предшественников})$$