Минимальная стоимость выполнения заданных задач, если указана стоимость 1, 7 и 30 дней

Дан отсортированный массив arr[] , состоящий из N положительных целых чисел, таких, что arr[i] представляет дни, в которые рабочий будет работать, и массив cost[] размера 3 , представляющий зарплату, выплаченную рабочим за 1 день , 7 дней и 30 дней соответственно, задача состоит в том, чтобы найти минимальную стоимость, необходимую для содержания работника за все заданные дни в arr[] .

Примеры:

Input: arr[] = [2, 4, 6, 7, 8, 10, 17], cost[] = [3, 8, 20]
Output: 14
Explanation:
Below is one of the possible ways of hiring workers with minimum cost:

1. On day 2, call a worker for 1 day which costs cost[0] = 3.
2. On day 4, call a worker for 7-day which costs cost[1] = 8, which covers day 4, 5, …, 10.
3. On day 17, call worker for 1-day which costs cost[0] = 3, which covers day 17.

Therefore, the total cost is 3 + 8 + 3 = 14, which is minimum among all possible combinations of hiring workers.

Input: arr[]= [1, 2, 3, 4, 6, 7, 8, 9, 11, 15, 20, 29], cost = [3, 8, 10]
Output: 10

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

• Инициализируйте массив, скажем, dp[] , где dp[i] хранит минимальную стоимость, необходимую для наличия работника в дни [i, arr[N – 1]] .
• Инициализируйте значение dp[arr[N – 1]] как минимум {cost[0], cost[1], cost[2]} .
• Инициализируйте переменную, скажем ptr , которая указывает на текущий элемент массива arr[] .
• Переберите диапазон [arr[N – 1] – 1, 0], используя переменную i , и выполните следующие шаги:
  1. Если значение ptr >= 0 и arr[ptr] == i , то
     • Инициализируйте переменную, скажем, val1 , и измените значение как dp[i + 1] + cost[0] .
     • Инициализируйте переменную, скажем, val2 , и измените значение как dp[i + 7] + cost[1] .
     • Инициализируйте переменную, скажем, val3 и измените значение как dp[i + 30] + cost[2] .
     • Теперь обновите значение dp[i] как минимум {val1, val2, val3} .
     • Уменьшите значение ptr на 1 .
  2. В противном случае обновите значение dp[i] как dp[i + 1] .
• После выполнения вышеуказанных шагов выведите в качестве результата значение dp[1] .

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

Временная сложность: O(M), где M — максимальный элемент массива .
Вспомогательное пространство: O(M)