Найдите минимальное количество блоков, которые будут покрывать вал, чтобы он восстанавливал все поврежденные блоки?

Question

Дорога, разделенная на блоки «_ * * _ _ _ _ _ _», где «*» представляет поврежденный блок. Существует рулон, который используется для ремонта дороги. Ролла имеет фиксированную длину K. Учитывая, что поврежденные места (N) и размер валка K. определяют минимальное количество блоков, которые будут покрывать вал, чтобы он ремонтировал все поврежденные блоки. Rolar не может постоянно ремонтироваться. Там могут быть пробелы. you can read it here.

Answer 1

Скажем, что поврежденные позиции представляют собой pos [0], pos [1], ..., pos [n-1]. Создайте массив dp. Здесь dp [idx] представляет минимальное количество блоков, которые будет покрывать валик для восстановления повреждений с индекса idx до n-1, и начинается с индекса idx. Теперь dp [n-1] = k; Для любого другого индекса, скажем, i, вычислим dp [i]: Если ролик удерживается в положении [i], ролик будет закрыт до позиции [i] + k. Предположим, что поврежденное место после pos [i] + k имеет индекс j. Теперь возможны два случая. 1. Ролик свертывается до того, что покрывает индекс j. ans1 = dp [j + 1] + (pos [j] -pos [i]) 2. Ролик снова начинается с индекса j. ans2 = dp [j] + k Затем dp [i] = min (ans1, ans2) Поиск индекса может быть выполнен с использованием двоичного поиска. Итак, общая временная сложность: O (n * log (n)).