Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот…
- 1
Обозначим через $m_{i,j}$ минимальную, а через $M_{i,j}$ максимальную сумму бонусов на пути из левой верхней клетки в клетку $(i,j)$.
- 2
Начальные значения для левой верхней клетки равны её бонусу: она входит в сумму маршрута.$$m_{1,1}=M_{1,1}=b_{1,1}$$
Ещё 3 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам только вправо или вниз. Между соседними клетками могут быть внутренние стены, через которые…
- 1
Создаём две таблицы динамического программирования: одну для максимальной суммы, другую для минимальной суммы монет при достижении каждой клетки.$$M_{i,j}=\text{максимальная сумма},\quad m_{i,j}=\text{минимальная сумма}$$
- 2
Для каждой клетки рассматриваем переход сверху и переход слева. Переход учитывается только в том случае, если между клетками нет стены.$$M_{i,j}=a_{i,j}+\max(\text{доступные значения }M),\quad m_{i,j}=a_{i,j}+\min(\text{доступные значения }m)$$
Ещё 2 шага — в полном решении
23ФИПИ 35A500№ 18Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот делает только перемещения вправо и вниз, поэтому в каждую клетку он может попасть только из клетки сверху или из клетки слева.
- 2
Для каждой клетки строим две таблицы: максимальную и минимальную сумму монет на пути от начальной клетки до данной клетки.$$\mathrm{maxSum}_{i,j}=a_{i,j}+\max(\mathrm{maxSum}_{i-1,j},\mathrm{maxSum}_{i,j-1})$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот…
- 1
Создаём две таблицы динамического программирования: в первой храним минимальную, во второй — максимальную сумму бонусов для каждого достижимого маршрута от левой верхней клетки до текущей.
- 2
Для каждой клетки рассматриваем переход из верхней клетки и из левой клетки. Переход исключается, если между клетками есть стена.
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот движется только вправо и вниз, поэтому в клетку можно попасть только из клетки сверху или из клетки слева, если между клетками нет стены.
- 2
Для каждой клетки строятся два значения: максимальная и минимальная сумма монет на допустимом пути от начальной клетки до этой клетки.$$max[i][j] = a[i][j] + \max\limits_{(k,l)\to(i,j)} max[k][l]$$
Ещё 3 шага — в полном решении
26ФИПИ 49567F№ 18Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Разобьём задачу на подзадачи: для каждой клетки вычислим минимальную и максимальную сумму платы на пути из левой верхней клетки в эту клетку.$$m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$
- 2
Аналогично вычислим максимальную сумму для каждой клетки.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
Ещё 2 шага — в полном решении
27ФИПИ 4B5A0B№ 18Повышенная Квадрат разлинован на $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
Максимальная сумма в правой нижней клетке равна $41$.$$M_{4,4}=41$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот…
- 1
Создайте для каждой клетки две величины: минимальную и максимальную сумму бонусов на пути из левой верхней клетки в эту клетку.
- 2
Для начальной клетки обе величины равны бонусу этой клетки.$$F_{1,1}^{\min}=F_{1,1}^{\max}=a_{1,1}$$
Ещё 3 шага — в полном решении
29ФИПИ 55978c№ 18Повышенная Квадрат разлинован на $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
Для примера максимальные суммы по строкам имеют вид: $1, 9, 17, 21$; $11, 20, 21, 24$; $12, 23, 33, 35$; $14, 26, 38, 44$.
Ещё 3 шага — в полном решении
30ФИПИ 5D4CE0№ 18Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот может попасть в каждую клетку только из клетки сверху или из клетки слева.$$S_{i,j}=a_{i,j}+S_{\text{предыдущая клетка}}$$
- 2
Для максимальной суммы в каждой клетке сохраняем большее из двух возможных накопленных результатов.$$\mathrm{max}_{i,j}=a_{i,j}+\max(\mathrm{max}_{i-1,j},\mathrm{max}_{i,j-1})$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Считаем для каждой клетки две величины: максимальную и минимальную сумму монет на пути из левой верхней клетки в эту клетку. Начальная клетка получает значение, равное номиналу монеты в ней.$$M_{1,1}=m_{1,1},\quad L_{1,1}=m_{1,1}$$
- 2
Для каждой клетки рассматриваем только те клетки, из которых в неё можно перейти: верхнюю, если между клетками нет горизонтальной стены, и левую, если между клетками нет вертикальной стены.$$M_{i,j}=m_{i,j}+\max\limits_{(k,l)\to(i,j)} M_{k,l},\quad L_{i,j}=m_{i,j}+\min\limits_{(k,l)\to(i,j)} L_{k,l}$$
Ещё 2 шага — в полном решении
32ФИПИ 6999A7№ 18Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот может попасть в клетку только сверху или слева, поэтому для каждой клетки заполняются две таблицы: максимальных и минимальных сумм.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
- 2
Для минимальной суммы используется тот же переход с операцией минимума.$$m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$
Ещё 2 шага — в полном решении
33ФИПИ 72C252№ 18Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам только вправо или вниз. Между соседними клетками могут быть внутренние стены, сквозь которые…
- 1
Построим таблицу максимальных сумм. Для каждой клетки складываем её значение с большим из значений, полученных из клетки сверху и клетки слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
- 2
Для правой нижней клетки максимальная сумма получается равной $41$.
Ещё 2 шага — в полном решении
34ФИПИ 779E0A№ 18Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам только вправо или вниз. Между соседними клетками могут быть внутренние стены, через которые…
- 1
Сначала вычислим максимальные суммы для путей до каждой клетки. В первой строке и первом столбце путь однозначен.$$M_{1,1}=1$$
- 2
Для остальных клеток прибавляем значение монеты к большему из двух возможных предыдущих результатов.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
Ещё 3 шага — в полном решении
35ФИПИ 79404A№ 18Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться только вправо или вниз. Между соседними клетками могут быть внутренние стены, сквозь которые Робот…
- 1
Заполняем таблицу максимальных сумм. В каждой клетке прибавляем стоимость монеты к большему из значений сверху и слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
- 2
Для правой нижней клетки максимальная сумма получается равной $41$.$$M_{4,4}=41$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот начинает движение из левой верхней клетки и может перемещаться только вправо или вниз. Между соседними клетками могут…
- 1
Сначала считываем из файла стоимость монет в каждой клетке и наличие стен между соседними клетками.
- 2
Для каждой клетки храним два значения: максимальную и минимальную сумму, которую можно получить при попадании в эту клетку из левой верхней клетки.
Ещё 3 шага — в полном решении
37ФИПИ A12AAD№ 18Повышенная Квадрат разлинован на $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
Таблица максимальных сумм имеет вид:$$\begin{matrix}1&9&17&21\\11&10&18&24\\12&15&30&32\\14&18&35&41\end{matrix}$$
Ещё 3 шага — в полном решении
38ФИПИ A83833№ 18Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). В каждой клетке указан натуральный бонус, не превышающий 100. Исполнитель Робот начинает движение из левой верхней клетки и может за одно…
- 1
Обрабатываем клетки построчно, начиная с левой верхней. Для каждой клетки храним две величины: минимальную и максимальную сумму бонусов на допустимом пути из начальной клетки.
- 2
Для клетки с бонусом $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}$$
Ещё 2 шага — в полном решении
39ФИПИ Ae45c9№ 18Повышенная Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот начинает в левой верхней клетке и забирает монету из неё. Для каждой последующей клетки рассматриваем только переходы слева и сверху, если между клетками нет стены.$$M_{i,j}^{\max}=a_{i,j}+\max(M_{i-1,j}^{\max},M_{i,j-1}^{\max})$$
- 2
Аналогично вычисляем минимальную возможную сумму для каждой клетки.$$M_{i,j}^{\min}=a_{i,j}+\min(M_{i-1,j}^{\min},M_{i,j-1}^{\min})$$
Ещё 1 шаг — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот…
- 1
Робот движется только вправо и вниз, поэтому в клетку он может попасть только из клетки сверху или из клетки слева.
- 2
Для каждой клетки строим два значения: минимальную и максимальную сумму бонусов на пути из левой верхней клетки в эту клетку.
Ещё 2 шага — в полном решении