Минимизируйте затраты на преобразование всех нулей в 1, при этом стоимость преобразования группы нулей равна X, а 1 — X/3.

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

Дана двоичная строка str , состоящая всего из двух символов ' 1 ' и ' 0 ', и целое число X , задача состоит в том, чтобы вычислить минимальную стоимость преобразования всех символов в '1'. Стоимость преобразования одного «0» в «1» определяется как X , а стоимость преобразования одного «1» в «0» равна X /3 . Если «0» преобразуется в «1», то все 0 , смежные с ним, как группа слева и справа от него, будут преобразованы в «1» без каких-либо затрат.

Пример:

Input: str = “101001”, X = 6
Output: 8
Explanation: Replace the character at index 2 i.e ‘1’ with ‘0’ which will take 6 / 3 =2 cost, then change it back to ‘1’ with the cost of 6 so that the string becomes “111111”

Input: str = “10110100”, X = 3 
Output:  6

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

  • Объявить массив dp[] для хранения рассчитанных ответов
  • Инициализируйте первый элемент с помощью INT_MAX
  • Если первый символ строки равен ' 0 ', повторно инициализируйте первый элемент dp[] с помощью K .
  • Перейдите строку str и проверьте следующие условия:
    • Если символ ' 1 ' и если dp[i-1] не равно INT_MAX, увеличьте сумму на 1
    • В противном случае, если символ равен ' 0 ':
      • dp[i-1] равно INT_MAX , установите dp[i] = k
      • Если предыдущий символ не был равен ' 0 ', вычислить минимальное значение и присвоить его dp[i]
  • Вернуть dp[N] , который является желаемым ответом

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

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

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