Рассмотрим две строки A = «qpqrr» и B = «pqprqrp». Пусть x — длина самой длинной общей подпоследовательности (не обязательно смежной) между A и B, и пусть y — количество таких самых длинных общих подпоследовательностей между A и B. Тогда x + 10y = ___.
(А) 33
(Б) 23
(С) 43
(D) 34
Ответ: (D)
Объяснение: // LCS имеет длину 4. Есть 3 LCS длиной 4 «qprr», «pqrr» и qpqr
Подпоследовательность — это последовательность, которая может быть получена из другой последовательности, выбрав из нее ноль или более элементов без изменения порядка оставшихся элементов. Подпоследовательность не должна быть смежной. Поскольку длина заданных строк A = «qpqrr» и B = «pqprqrp» очень мала, нам не нужно строить матрицу 5 × 7 и решать ее с помощью динамического программирования. Скорее мы можем решить это вручную просто грубой силой. Сначала мы проверим, существует ли подпоследовательность длины 5, так как min_length (A, B) = 5.
Рекомендуемые посты:
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
- ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
- ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65
0.00 (0%) 0 votes