Если вы считаете, что есть только две целочисленные переменные, i, j с 0 <= i <= M, 0 <= j <= N, вы, вероятно, можете решить это с помощью динамического программирования. Я постараюсь написать это ясно и без движка LaTeX, поэтому, пожалуйста, потерпите меня.
Скажем, что вы создали четыре M * N матрицы целых чисел G, R, V и L. Для каждой точки (i, j), g_ij обозначают количество зеленых фигур на этом квадрате, а r_ij количество красных фигур. v_ij обозначает количество зеленых фигур в прямоугольнике (0, 0) - (i, j) или 0, если количество красных фигур слишком велико, а l_ij обозначает количество красных фигур в прямоугольнике или бесконечность, если исходное значение шло превышать лимит. Если я говорю о значении ячейки, я имею в виду v_ij, предел ячейки эквивалентен l_ij.
Начиная с точки (0, 0), подход к программированию будет следующим:
- Дано очко
(i, j)
- Возможные направления до
(i + 1, j) и вправо до (i, j + 1).
- Для
(i + i, j) количество красных фигур в прямоугольнике, l_(i + 1)j, равно пределу предыдущей ячейки l_ij + количество красных фигур в ряду над прямоугольником, поэтому ячейки * С 1035 * по (i + 1, j). Если вы используете предел l_ij, вам не нужно вычислять сумму (i + 1) * j ячеек за один шаг, а только сумму j + 1 ячеек - j ячеек в строке плюс одно сохраненное значение. То же самое касается расчета v_(i + 1)j, просто используйте сохраненное значение v_ij плюс количество зеленых фигур в верхнем ряду.
- Если предельное количество красных фигур превышено, вы можете создать прямоугольник между
(i + 1, j) и верхним правым углом (M, N) и назначить предел всех этих ячеек как превышенный - потому что все возможные прямоугольники, которые могут быть сформированы там должен содержать прямоугольник (0, 0) - (i + 1, j) и, следовательно, он должен содержать слишком много красных кусочков. Расчеты для правильного хода очень похожи.
- Как только больше не будет неизвестных частей, просто найдите самое высокое значение в V за O (MN), и все готово.
Что касается вашего второго вопроса, возможное приближение будет состоять в том, чтобы сделать шаг размером от 0 до 1 и разделить все значения на этот шаг, а затем округлить, так что (2/3, 7/5) с размером шага 1/10 станет (6, 14). Затем примените алгоритм, используя эти шаги. Вы можете запускать его несколько раз, уменьшая размеры шагов, сохраняя и преобразовывая матрицу V между прогонами, чтобы избежать многих вычислений. Я надеюсь, что это помогло!
ОБНОВЛЕНИЕ : теперь с примером выполнения
Например, в каждой ячейке (x, y) обозначает количество зеленых и красных кусочков соответственно. Рядом с ней находятся матрицы G и R - пустые значения означают 0.
Ограничение на количество красных фигур - 3.
G R
+-----+-----+-----+-----+ +---+---+---+---+ +---+---+---+---+
3 |(1,2)| | |(4,0)| 3 | 1 | | | 4 | 3 | 2 | | | |
+-----+-----+-----+-----+ +---+---+---+---+ +---+---+---+---+
2 | |(3,1)| |(1,2)| 2 | | 3 | | 1 | 2 | | 1 | | 2 |
+-----+-----+-----+-----+ +---+---+---+---+ +---+---+---+---+
1 |(1,1)|(1,1)| | | 1 | 1 | 1 | | | 1 | 1 | 1 | | |
+-----+-----+-----+-----+ +---+---+---+---+ +---+---+---+---+
0 | |(0,1)|(3,1)|(1,1)| 0 | | | 3 | 1 | 0 | | 1 | 1 | 1 |
+-----+-----+-----+-----+ +---+---+---+---+ +---+---+---+---+
0 1 2 3 0 1 2 3 0 1 2 3
Начиная с (0, 0), у нас есть 0 красных и 0 зеленых частей, поэтому V и L выглядят следующим образом:
V L
+---+---+---+---+ +---+---+---+---+
3 | | | | | 3 | | | | |
+---+---+---+---+ +---+---+---+---+
2 | | | | | 2 | | | | |
+---+---+---+---+ +---+---+---+---+
1 | | | | | 1 | | | | |
+---+---+---+---+ +---+---+---+---+
0 | 0 | | | | 0 | 0 | | | |
+---+---+---+---+ +---+---+---+---+
0 1 2 3 0 1 2 3
Для полноты я заполняю нулевые значения в V и L.
Теперь мы можем подняться до (1, 0) и вправо до (0, 1). Мы получаем l_10 = l_00 + r_10 = 0 + 1 = 1 и v_10 = v_00 + g_10 = 0 + 1 = 1. Справа мы получаем l_01 = l_00 + r_01 = 0 + 1 = 1 и v_01 = v_00 + g_01 = 0. Это дает нам следующую ситуацию:
V L
+---+---+---+---+ +---+---+---+---+
3 | | | | | 3 | | | | |
+---+---+---+---+ +---+---+---+---+
2 | | | | | 2 | | | | |
+---+---+---+---+ +---+---+---+---+
1 | 1 | | | | 1 | 1 | | | |
+---+---+---+---+ +---+---+---+---+
0 | 0 | 0 | | | 0 | 0 | 1 | | |
+---+---+---+---+ +---+---+---+---+
0 1 2 3 0 1 2 3
Теперь мы можем подняться с (1, 0), прямо с (1, 0), что эквивалентно повышению с (0, 1), и мы можем перейти с (0, 1).
Если мы поднимемся с (1, 0) до (2, 0), мы получим l_20 = l_10 + r_20 = 1 + 0 = 1 и v_20 = v_10 + g_20 = 1 + 0 = 1. Если мы пойдем прямо от (1, 0) до (1, 1), мы получим l_11 = l_10 + r_01 + r_11 = 1 + 1 + 1 = 3. Обратите внимание, что это точно так же, как повышение от (0, 1), до l_11 = l_01 + r_10 + r_11 = 1 + 1 + 1 = 3. Точно так же v_11 = v_10 + g_01 + g_11 = 1 + 1 = 2. Наконец, если мы перейдем прямо от (0, 1) до (0, 2), мы получим l_02 = l_01 + r_02 = 1 + 1 = 2 и v_02 = v_01 + g_02 = 0 + 3 = 3. Это приводит к следующей схеме:
V L
+---+---+---+---+ +---+---+---+---+
3 | | | | | 3 | | | | |
+---+---+---+---+ +---+---+---+---+
2 | 1 | | | | 2 | 1 | | | |
+---+---+---+---+ +---+---+---+---+
1 | 1 | 2 | | | 1 | 1 | 3 | | |
+---+---+---+---+ +---+---+---+---+
0 | 0 | 0 | 3 | | 0 | 0 | 1 | 2 | |
+---+---+---+---+ +---+---+---+---+
0 1 2 3 0 1 2 3
Теперь мы можем подняться с (2, 0), прямо с (2, 0), что эквивалентно повышению с (1, 1), прямо с (1, 1), что эквивалентно повышению с (0, 2), или прямо с (0, 2). Если мы поднимемся с (2, 0) до (3, 0), мы получим l_30 = l_20 + r_30 = 1 + 2 = 3 и v_30 = v_20 + g_30 = 1 + 1 = 2.Мы можем вычислить (2, 1), поднявшись от (2, 0), но поднявшись от (1, 1), мы можем сделать то же самое с большей частью предварительно вычисленного прямоугольника (4 ячейки вместо 3). Мы получаем l_21 = l_11 + r_20 + r_21 = 3 + 0 + 1 = 4. Поскольку это превышает предел, v_21 = 0. Теперь любой прямоугольник, содержащий (2, 1), будет иметь те же самые ячейки, что и (2, 1), включая те, которые содержат до 4 красных частей. Следовательно, все прямоугольники, содержащие (2, 1), должны быть недействительными. Это все ячейки с x >= 2 и y >=1. Мы даем им l_xy = Inf для ясности.
Ячейка (1, 2) содержит (0, 0), но, поскольку l_12 = l_11 + r_02 + r_12 = 3 + 1 + 0 = 4, ячейка недействительна, как и (1, 3), следуя той же логике, что и выше.
Наконец, если мы пойдем прямо от (0, 2) до (0, 3), мы получим l_03 = l_02 + r_03 = 2 + 1 = 3 и v_03 = v_02 + g_03 = 3 + 1 = 4. Это приводит к следующей схеме:
V L
+---+---+---+---+ +---+---+---+---+
3 | 2 | 0 | 0 | 0 | 3 | 3 |Inf|Inf|Inf|
+---+---+---+---+ +---+---+---+---+
2 | 1 | 0 | 0 | 0 | 2 | 1 |Inf|Inf|Inf|
+---+---+---+---+ +---+---+---+---+
1 | 1 | 2 | 0 | 0 | 1 | 1 | 3 |Inf|Inf|
+---+---+---+---+ +---+---+---+---+
0 | 0 | 0 | 3 | 4 | 0 | 0 | 1 | 2 | 3 |
+---+---+---+---+ +---+---+---+---+
0 1 2 3 0 1 2 3
Итак, как вы можете видеть, прямоугольник с наибольшим значением - это прямоугольник, сформированный с точками (0, 3) со значением 4, и мы выяснили это при вычислении только 10 из 16 ячеек. Конечно, верхняя граница для этого алгоритма O(MN), но на практике это неизбежно, потому что рассмотрим случай, когда нет красных фигур или предел очень высок. Тогда вы все равно должны вычислить сумму всех M * N клеток.