Решения заданий ФИПИ ЕГЭ по информатике: «Динамическое программирование» — с ответами

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

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

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

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

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

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

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

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

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

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

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

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

В начальной клетке минимальная и максимальная суммы равны стоимости этой клетки: $1$.

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

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

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

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

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

Обозначим через $S_i$ сумму первых $i$ элементов последовательности, где $S_0=0$. Сумма элементов подпоследовательности от $l+1$ до $r$ равна $S_r-S_l$.$$S_r-S_l$$

Эта сумма кратна $71$, если префиксные суммы имеют одинаковые остатки при делении на $71$.$$S_r \equiv S_l \pmod{71}$$

Перебор всех троек позиций имеет слишком большую сложность, поэтому состояния нужно обновлять при одном проходе по файлу.$$O(N^3)$$

Пусть $a_i$ — показание в момент $i$. Для каждой позиции поддерживаем минимальную сумму одного, двух и трёх выбранных показаний, причём последние выбранные позиции удовлетворяют ограничению по расстоянию.$$d_1(i)=a_i$$

Пусть $a_i$ — значение показания в момент $i$. Для каждого момента нужно учитывать только показания с индексами не больше $i-K$, поскольку между выбранными моментами должно пройти не менее $K$ минут.$$j \leq i-K$$

Вычисляем лучшие суммы для последовательностей из одного и двух показаний. Для двух показаний к текущему значению добавляется лучший результат для одного показания среди допустимых предыдущих позиций.$$dp_1[i]=a_i,\qquad dp_2[i]=a_i+\max_{j\leq i-K}dp_1[j]$$

Нумеруем показания от $0$ до $N-1$. Для текущего показания $a_i$ предыдущие выбранные показания должны иметь индексы не больше $i-K$.

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