Задана последовательность из n элементов, A1, A2, ..., An. Удалите наименьшее количество цифр, чтобы сделать массив неубывающим - PullRequest
Новая
       32

Задана последовательность из n элементов, A1, A2, ..., An. Удалите наименьшее количество цифр, чтобы сделать массив неубывающим

0 голосов
/ 23 февраля 2020

При заданной последовательности n элементов, A 1 , A 2 , ..., A n

  • n ≤ 1000
  • Пусть ndigits (x) - количество цифр x
    • Например:
    • ndigits (10000) = 5
    • ndigits (123) = 3
    • ndigits (9) = 1
  • Гарантируется, что сумма ndigits (A i ) ≤ 10 5 где 1 ≤ i ≤ n.
    • , что означает ndigits (A 1 ) + ndigits (A 2 ) + ... + ndigits (A n ) ≤ 10 5

Удалите наименьшее количество цифр, чтобы последовательность не уменьшалась. Распечатайте количество удаленных цифр.

Например:

  • n = 4
  • A = [93, 31, 23, 31]
  • Удалите полужирные цифры, чтобы сделать последовательность неубывающей:
  • A = [ 9 3, 3 1 , 23, 31] → A = [ 3, 3, 23, 31]
  • Ответ 2 (удалите две цифры 1 и 9)

Я попытался наивным алгоритмом:

  • Для каждого элемента от n-1 до 1, пусть этот элемент A i удаляет наименьшее количество цифр, чтобы сделать эти элементы самыми большими, но меньшими, чем A i + 1 (** *)
  • Используйте грубую силу и проверьте условие (***) (которое занимает O (2 сумма ndigits ) времени).

Есть ли лучший алгоритм?

1 Ответ

1 голос
/ 24 февраля 2020

Это можно решить с помощью динамического программирования c.

Давайте сначала выясним, как удалять цифры. Используйте двоичное число и в зависимости от позиции 1 уберите di git в этой позиции в данном номере. Пример прояснит ситуацию:

Удалить-маскировать число с помощью j:

Позвольте j = 2 - его двоичное представление - 10, вы удаляете число в позиции, где оно 1. Например, для числа 93 удаление-маскирование его с помощью 2 приведет к 3, удаление-маскирование его с помощью 3 само приведет к 93, потому что вы не можете удалить все числа! удалив маску с помощью 1, вы получите 9. Я надеюсь, что вы поняли.

Диапазон j:

Диапазон j будет только от 0 до 63, потому что самое большое число в вашем вводе - 10^5 и имеет максимум 6 цифр, а наибольшая длина двоичного числа с 6 цифрами - 63.

Алгоритм:

Позвольте dp[i-1][j] представлять количество удалений, которые требуются для создания неубывающей подпоследовательности, когда (i-1) th число маскируется при удалении числом j. Если его невозможно сделать неубывающим - это что-то вроде MAX_VALUE

Обновление dp[i][j]:

Теперь, чтобы получить dp[i][j], вам нужно сравнить все dp[i-1][k] с dp[i][j] и обновите следующим образом: 

for j = 0 to 63:
    if (length of binary representation of j <= length of the ith number ):
       dp[i][j] = MAX_VALUE
       for all k = 0 to 63:
          if dp[i-1][k] != MAX and (ith number after delete-masking with j) >= (i-1th number after delete-masking with k) : 
          dp[i][j] = min(dp[i][j], dp[i-1][k] + (bitcount of j))

Вы получаете эти значения вплоть до arr.length-1, а затем берете минимум всех dp[arr.length-1][j] для j = 0 to 63

Базовое условие: Если длина входного массива больше 1:

dp[0][j] = (bitcount of j) if length of binary representation of j <= length of the number arr[0]

Рабочий пример показан здесь

...