Месклиниты собрались отправиться в экспедицию на край света. У них есть корабль, состоящий из сетки из n×m плотиков

Жужа

38

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

Для решения этой задачи мы можем использовать подход динамического программирования. Создадим двумерный массив динамического программирования dp размером (n+1) x (m+1), где dp[i][j] будет представлять максимальное количество месклинитов, которые можно разместить на первых i плотиках, имея mассу m.

Изначально все ячейки dp будут равны нулю. Начнем заполнять массив dp с помощью простого алгоритма.

1. Зададим базовые случаи. Для первой строки и первого столбца dp[i][0] и dp[0][j] будут равны нулю, так как на них не может поместиться ни один месклинит.

2. Переберем все возможные плотики и массы месклинитов от 1 до n и от 1 до m соответственно.

3. Если грузоподъемность выбранного плотика больше или равна массе месклинита, то dp[i][j] можно вычислить следующим образом: dp[i][j] равно максимуму между текущим значением dp[i][j] и dp[i-1][j-1] + 1. Это означает, что мы можем добавить месклинита на текущий плотик, увеличив максимальное количество на 1.

4. Если грузоподъемность выбранного плотика меньше массы месклинита, то dp[i][j] равно максимуму между текущим значением dp[i][j] и dp[i-1][j]. Это означает, что мы не можем добавить текущего месклинита на плотик, поэтому максимальное количество остается без изменений.

5. В конечном итоге, dp[n][m] содержит максимальное количество месклинитов, которое можно взять с собой в экспедицию.

Приведенный ниже код решает задачу с помощью описанного алгоритма:

python

n, m = map(int, input().split())



# Создание двумерного массива dp и заполнение его нулями

dp = [[0] * (m + 1) for _ in range(n + 1)]



for i in range(1, n + 1):

    for j in range(1, m + 1):

        weight = int(input())

        

        if weight <= j:

            # dp[i][j] равно максимуму между текущим значением dp[i][j] и dp[i-1][j-1] + 1

            dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)

        

        # dp[i][j] равно максимуму между текущим значением dp[i][j] и dp[i-1][j]

        dp[i][j] = max(dp[i][j], dp[i-1][j])



# Вывод максимального количества месклинитов

print(dp[n][m])

Объяснение решения:
Мы создаем массив dp размером (n+1) x (m+1), чтобы учесть базовые случаи и удобно работать с индексами. Затем мы перебираем все плотики и месклинитов и проверяем условие грузоподъемности плотика и массы месклинита. Если условие выполняется, мы обновляем значение dp[i][j] в соответствии с описанным алгоритмом. В конце мы выводим значение dp[n][m], которое содержит максимальное количество месклинитов.