Информатика ЕГЭ — решения заданий ФИПИ с ответами

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

Для клетки с бонусом $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{ предшественников})$$

Используем динамическое программирование: в каждой клетке вычисляем максимальную и минимальную суммы монет на пути из левой верхней клетки.$$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$, $18$, $35$, $41$.

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

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

Обозначим бонус клетки в строке $i$ и столбце $j$ через $a_{i,j}$. Для каждой клетки создадим два значения: минимальную и максимальную суммы бонусов на допустимом пути от начальной клетки.$$mn_{i,j}=\min\text{ допустимых сумм},\quad mx_{i,j}=\max\text{ допустимых сумм}$$

В начальной клетке оба значения равны её бонусу. Если в клетку можно попасть сверху, учитываем значение из клетки над ней; если слева — из клетки слева. Переход через утолщённую границу запрещён.$$mn_{i,j}=a_{i,j}+\min(mn_{i-1,j},mn_{i,j-1}),\quad mx_{i,j}=a_{i,j}+\max(mx_{i-1,j},mx_{i,j-1})$$

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

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

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

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