Использование динамического программирования с решением Python: давайте узнаем, как думать о цветных прямоугольниках, проблеме codeforces с 1800 точками.

Понимание проблемы

Цветные прямоугольники — задача на codeforces на 1800 баллов, надеюсь, вы внимательно прочитали задачу и попробовали ее решить. Эта задача в основном требует получения наибольшей площади цветных прямоугольников. Вопрос в том, как получить такую ​​большую площадь и какие данные мы имеем в этой задаче.

Вам даны пары цветных палочек (красная, зеленая и синяя), и вы знаете длину каждой пары. Чтобы вычислить площадь этого прямоугольника, нужно умножить длину на ширину. Скажем, у нас есть одна пара длины 3 (что означает 2 параллельные стороны длины 3) и другая пара длины 4 (что означает 2 параллельные стороны длины 4), поэтому они могут образовать прямоугольник, площадь которого равна 12.

Входы

Эта задача имеет четыре входа:

  • R, G и B — количество красных, синих и зеленых пар палочек соответственно.
  • Длины красных пар палочек
  • Длины синих пар палочек
  • Длины зеленых пар палочек

Почему это делается с помощью динамического программирования?

Сначала эта задача кажется тривиальной, поэтому, если у вас есть 3, 4, 5 длин красных, синих и зеленых пар палочек. Кажется, мы должны вычислить площадь для каждой возможной комбинации, а затем сравнить их, чтобы увидеть максимальную площадь, которая равна 20 (4 * 5). Но что, если у нас есть тот же набор пар плюс 6 пар зеленых палочек, что означает, что мы имеем:

  • rl = [3]
  • gl = [4, 6]
  • bl = [5]

где каждый из rl, gl, bl соответствует списку красных, синих и зеленых палочек соответственно

В этом случае мы должны заботиться о порядке выбора чисел, которые мы выбираем для вычисления площади, что означает сначала выбор самых высоких чисел, что подразумевает сортировку каждого массива, чтобы мы могли сначала умножать самые большие числа. Таким образом, при решении этого вопроса наилучшая площадь будет равна 42 (что равно 6 * 5 + 3 * 4).

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

  • rl = [3]
  • gl = [2, 2]
  • bl = [3]

Это означает, что если мы применим то, что мы сделали в последнем примере, мы получим 9 (что равно 3 * 3), и это потому, что 3 и 3 являются самыми большими числами, а если мы рассмотрим умножение 3 на 2, а затем 2 на 3, мы получим 12, что явно большая площадь. В этом случае следует рассмотреть способ хранения продуктов каждой комбинации и принять решение о расчете наилучшей площади.

Это можно сделать с помощью динамического программирования. Сначала нам нужно сформировать трехмерный массив для хранения вычисленных областей, чтобы иметь возможность их сравнивать.

Эта проблема может быть более сложной, если у нас есть:

  • rl = [10, 3, 2]
  • gl = [8, 6, 4]
  • bl = [8, 6, 2]

Я уже отсортировал каждый массив в порядке убывания. Представьте, что это стеки, и каждый элемент, который вы умножаете, выталкивается из него (удаляется). Ниже приводится рекомендуемый способ выполнения умножения:

  1. 10 * 8 (из rl и bl)
  2. 8 * 6 (из bl и gl)
  3. 6 * 3 (из gl и rl)
  4. 2 * 4 (из rl и gl)

Если вы посчитаете сумму этих площадей, вы получите 154, но это не самая большая площадь, поэтому предлагаемое решение неверно. Давайте посмотрим еще одно предлагаемое умножение:

  1. 10 * 8 (из rl и gl)
  2. 8 * 6 (из bl и gl)
  3. 6 * 4 (из bl и gl)
  4. 3 * 2 (из rl и bl)

Эта комбинация дает нам самую большую площадь, которая является правильным ответом. Если вы заметите разницу, вы увидите, что gl имеет [8, 6, 4], а bl имеет [8, 6, 2]. Похоже, что у нас здесь равные числа, поэтому возникает вопрос, как мы можем решить, какое число будет умножено первым. Должны ли мы сначала умножать то, что содержится в rl, на gl или rl на bl. Сравнивая два предлагаемых решения, первые 3 шага дают нам большее число. Общая площадь второго решения равна 158, что больше, чем у первого. Это произошло потому, что мы хотим оставить наименьшее число в конце массива bl. Вот почему мы сначала взяли то, что находится в rl и gl, прежде чем дойдем до конца синего массива. Это гарантирует, что нам нужен способ рекурсивного вычисления площади в каждом узле, чтобы мы могли решить, какой путь нам следует выбрать.

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

Вот как я думал об этой проблеме, и ниже представлена ​​реализация на Python, представленная srkvrm:

Питон

Мотивировано

Другие вещи для решения проблем

Если вы хотите увидеть больше сообщений в блоге о решении проблем, проверьте:



Решение проблем
Решение проблем, 26 августа 2020 г.www.ezzzeddinabdullah.com