Максимизируйте длину верхней границы, образованной размещением заданных N прямоугольников горизонтально или вертикально.

Опубликовано: 22 Сентября, 2022

Дан вектор пар, V[] обозначающий ширину и высоту N прямоугольников, пронумерованных от 1 до N , эти прямоугольники соприкасаются с горизонтальной осью и являются смежными слева направо в порядке номеров. Задача состоит в том, чтобы найти максимальную длину верхней границы, образованной размещением каждого из прямоугольников либо горизонтально, либо вертикально.

Примеры:

Input: N = 5, V[] = {{2, 5}, {3, 8}, {1, 10}, {7, 14}, {2, 5}} 
Output: 68
Explanation: Place the first and the third rectangle vertically and all the other rectangles horizontally to get the maximum length of the upper boundary. (5 + 6 + 3 + 7 + 10 + 13 + 7 + 12 + 5 = 68)

Input: N = 1, V[] = {{8, 7}}
Output: 8
Explanation: Place the only rectangle horizontally, so that the length of the upper boundary becomes 8.

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

Временная сложность: O(2 N )
Вспомогательное пространство: O(1)

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

  1. Поместите прямоугольник текущего переходного состояния горизонтально
  2. Поместите прямоугольник текущего переходного состояния вертикально

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

Определим dp[i][0] как максимальную верхнюю границу первых i прямоугольников, если i -й прямоугольник расположен горизонтально, и dp[i][1] как максимальную верхнюю границу первых i прямоугольников, если i -й прямоугольник размещены вертикально. Переходы определяются как:

Let height1= |V[i – 1].second – V[i].second| and height2 = |V[i – 1].first – V[i].second|
Then, dp[i][0]= max(height1+dp[i-1][0], height2+dp[i-1][1])+V[i].first

Let vertical1 = |V[i].first – V[i -1].second| and vertical2 = | V[i].first – V[i – 1].first|
then dp[i][1] = max(vertical1 + dp[i-1][0], vertical2 + dp[i-1][1]) + V[i].second

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте двумерный массив dp[][] размера N*2 . Инициализируйте dp[0][0] = V[0].first и dp[0][1] = V[0].second .
  • Перейдите через диапазон [1, N], используя переменную i , и выполните следующие шаги:
    • Инициализируйте переменные height1 = абсолютная разница V[i-1].second и V[i].second и height2 = абсолютная разница V[i-1].first и V[i].second . Также обновите значение dp[i][0] на V[i].first .
    • Добавьте max(dp[i-1][0]+height1, dp[i-1][1]+height2) к значению dp[i][0].
    • Инициализируйте dp[i][1] в V[i].second . Также инициализируйте переменные vertical1 = абсолютная разница V[i-1].first и V[i].first и vertical2 = абсолютная разница V[i-1].first и V[i].first .
    • Добавьте max(dp[i-1][0]+vertical1, dp[i-1][1]+vertical2) к значению dp[i][1] .
  • После выполнения вышеуказанных шагов выведите значение max(dp[N-1][0], dp[N-1][1]) .

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ