Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Используем динамическое программирование: в каждой клетке вычисляем максимальную и минимальную суммы монет на пути из левой верхней клетки.$$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})$$
- 2
Для таблицы из примера значения максимальных сумм в последней строке равны $14$, $18$, $35$, $41$.
Ещё 2 қадам — толық шешімде
Квадрат разлинован на $N \times N$ клеток, где $1 < N < 30$. Исполнитель Робот перемещается из левой верхней клетки в правую нижнюю, выполняя команды «вправо» и «вниз». Между соседними клетками…
- 1
Разобьём квадрат на клетки и будем обрабатывать их слева направо и сверху вниз: Робот движется только вправо и вниз.
- 2
Для каждой клетки вычислим максимальную сумму на допустимом пути. Если в клетку можно прийти из нескольких клеток, выбираем наибольшую сумму среди разрешённых переходов и прибавляем стоимость монеты текущей клетки.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
Ещё 2 қадам — толық шешімде
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот…
- 1
Обозначим бонус клетки в строке $i$ и столбце $j$ через $a_{i,j}$. Для каждой клетки создадим два значения: минимальную и максимальную суммы бонусов на допустимом пути от начальной клетки.$$mn_{i,j}=\min\text{ допустимых сумм},\quad mx_{i,j}=\max\text{ допустимых сумм}$$
- 2
В начальной клетке оба значения равны её бонусу. Если в клетку можно попасть сверху, учитываем значение из клетки над ней; если слева — из клетки слева. Переход через утолщённую границу запрещён.$$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})$$
Ещё 1 қадам — толық шешімде
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Считываем из электронной таблицы размер квадрата, стоимость монет в клетках и расположение внутренних стен.
- 2
Для каждой клетки вычисляем максимальную сумму, которую можно получить при попадании в неё из левой верхней клетки. Переходы через стены и недостижимые клетки не учитываются.$$F_{i,j}=a_{i,j}+\max(F_{i-1,j},F_{i,j-1})$$
Ещё 2 қадам — толық шешімде
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо…
- 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
В начальной клетке минимальная и максимальная суммы равны стоимости этой клетки: $1$.
- 2
Для каждой следующей клетки считаем две величины: минимальную и максимальную сумму на пути из левой верхней клетки. В клетку можно попасть только из верхней или левой клетки.$$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})$$
Ещё 2 қадам — толық шешімде
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 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})$$
Ещё 1 қадам — толық шешімде
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо…
- 1
Обозначим через $max[i][j]$ и $min[i][j]$ максимальную и минимальную суммы монет на пути из левой верхней клетки в клетку $(i,j)$.
- 2
Для каждой клетки рассмотрим переходы сверху и слева. Переход учитывается только в том случае, если между соответствующими клетками нет стены.
Ещё 3 қадам — толық шешімде
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот может прийти в клетку только из клетки сверху или из клетки слева. Поэтому для каждой клетки вычисляем максимальную и минимальную суммы, которые можно набрать при попадании в неё.$$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})$$
- 2
В первой строке и первом столбце значение накапливается единственным возможным маршрутом. Затем таблицы заполняются слева направо и сверху вниз.
Ещё 1 қадам — толық шешімде