Форум программистов, компьютерный форум CyberForum.ru

Задана строка, символы которой могут повторяться. Нужно удалить все символы строки с помощью наименьшего количества вычеркиваний - C++

Восстановить пароль Регистрация
 
Владислав_95
0 / 0 / 0
Регистрация: 30.09.2013
Сообщений: 5
15.03.2014, 14:55     Задана строка, символы которой могут повторяться. Нужно удалить все символы строки с помощью наименьшего количества вычеркиваний #1
Задана строка, символы которой могут повторяться. За один ход разрешается вычеркнуть в любом месте строки один или несколько одинаковых символов, идущих в строке подряд. Нужно удалить все символы строки с помощью наименьшего количества вычеркиваний.
Вход. Строка длиной не больше 255.
Выход. Минимальное количество операций, с помощью которых можно удалить все символы строки.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.03.2014, 14:55     Задана строка, символы которой могут повторяться. Нужно удалить все символы строки с помощью наименьшего количества вычеркиваний
Посмотрите здесь:

C++ удалить со строки все повторяющиеся символы
C++ Удалить из строки s1 все символы, встречающиеся в строке s2.
Удалить из строки все числовые символы C++
Дана строка. Удалить из строки все двойные символы. Пример: “asddewwf” → “asdewf” C++
C++ Определить длину строки,удалить из строки все символы, которые равны заданному
Удалить из строки все символы не являющиеся буквами латинского алфавита C++
Удалить из строки все символы не являющиеся латинскими буквами C++
Строки: удалить все символы, которые размещены между скобками C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mymedia
190 / 190 / 48
Регистрация: 27.05.2011
Сообщений: 543
15.03.2014, 16:40     Задана строка, символы которой могут повторяться. Нужно удалить все символы строки с помощью наименьшего количества вычеркиваний #2
Так? Я правильно понял?
C++
1
2
3
4
5
6
7
8
9
10
11
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
int main()
{
    using namespace std;
    string str;
    getline(cin,str);
    cout << distance(str.begin(), unique(str.begin(), str.end()));
}
Владислав_95
0 / 0 / 0
Регистрация: 30.09.2013
Сообщений: 5
16.03.2014, 08:05  [ТС]     Задана строка, символы которой могут повторяться. Нужно удалить все символы строки с помощью наименьшего количества вычеркиваний #3
Пример. Вход: 1343223; выход: 4.

Анализ задачи. В строке 1343223 из примера можно вычеркнуть 22 (получится

13433), затем 1 и 4, а затем сразу три символа 3, т.е. всего четыре вычеркивания.

Предварительно "сожмем" слово, заменив каждую последовательность одинако-

вых символов, идущих подряд, одним таким символом, например, из 111223114

получим 12314. Очевидно, что ответ от этого не изменится, как и время работы в

худшем случае. Однако в среднем выигрыш будет существенным за счет уменьшения

числа подзадач (сложность "сжатия" линейна и не влияет на общую оценку — см

задачу 5.4). Кроме того, "сжатие" гарантирует, что все соседние символы различны.

Пусть а [1] …а [т] — строка, т — ее длина. Часть строки a [i] …а [ j ], состоя-

щую из всех символов с i’-го по j-Vi включительно, будем называть i…/-подстрокой

Серия подзадач очевидна: За какое минимально возможное количество вычеркивании

можно удалить u.j-подстроку? Нужная задача будет одной из задач серии, а именно

задачей размером (1, т).

Тривиальные подзадачи, решение которых очевидно — это подзадачи вида (i, i

(одиночный символ удаляется за один ход) и вида (i, i+1) (двухсимвольные подстро-

ки, состоящие из разных символов, удаляются за два хода).

Обозначим минимальное количество действий для удаления {..у-подстроки

через Тц. Оптимальным решением нетривиальной (1,у)-подзадйчи может быть такое:

перебрать все к, удовлетворяющие i
подстроку.

Таким образом, при a\i] *а [ j ] окончательный оптимум (/,./)-подзадачи достаточ-

но искать как ТҐ= Kv (согласно (13.14)), а при a [i] = а [j] следует рассмотреть Ку

и ЛГ* и выбрать из них меньшее.

Но и этого мало. Если одинаковые крайние символы «’…/-подстроки повторяются

внутри нее, то может оказаться, что выгоднее всего сначала удалить все подстроки,

разделяющие эти вхождения, а затем зачеркнуть все эти символы за один ход

(например, слово 1213141 лучше всего обработать, вычеркнув 2, 3, 4, а затем все

единицы за один ход).

Однако "может оказаться" не означает "непременно окажется". Рассмотрим слово

1231413215161. Любое его оптимальное решение (например, сначала вычеркнуть 4,

затем новообразуемые подстроки 11, 33, 22, затем 5, б, и, наконец, оставшиеся 1111)

требует удалять вторую и третью справа единицы (в позициях 9 и 11) вместе с крайними

(в позициях 1 и 13), а единицы в позициях 4 и 6 должны быть вычеркнуты раньше. Таким

образом, на последний ход нужно оставить много единиц, но не все.

Может показаться, что для реализации этой идеи нужен полный перебор под-

множеств вхождений символов, одинаковых с a [i] и а [ j ]. Однако это не так бла-

годаря следующей идее.

Пусть для некоторой /../’-подстроки крайние символы a[i], a[j] совпадают

с некоторым внутренним а [к]. Тогда удаление сначала i+l..fc-1-подстроки, затем

k+\..j-\ – подстроки, затем трех одинаковых символов a[i]a[k]a[j] можно услов-

но свести к тому, что удаляется /..^-подстрока (но символ а [к] при этом загадочным

образом остается), а затем Ј. ../-подстрока. Из суммы количеств ходов по удалению

этих подстрок вычитается 1, поскольку при вычислении Т^+Т^ вычеркивание симво-

ла а [к] считается дважды:

Очевидно, что формула (13.16) позволяет собирать под одно вычеркивание много

одинаковых символов (если оптимальное решение хотя бы одной из (/,&)- и (k,j)-

подзадач получено по этой же формуле), не требуя, чтобы все одинаковые символы

вычеркивались обязательно за один раз.

Как и в задачах об умножении матриц и о максимальном значении выражения,

формулы (13.14)—(13.17) следует реализовать либо с помощью рекурсии с запомина-

нием, либо итеративно заполнить таблицу для 7^, двигаясь от главной диагонали по

линиям, параллельным ей, пока не придем в угловой элемент Т1т.

Вспомогательные величины Ку, K’tj и используются только для вычисления

Ту (при тех же i иу) и в дальнейшем их помнить не обязательно. Однако, реализуя

алгоритм с помощью рекурсии с запоминанием, эти вспомогательные значения все-

таки придется хранить (в массивах или в программном стеке). Так что преимущества

итеративного заполнения таблицы проявляются в данной задаче несколько ярче

чем в предыдущих.
Yandex
Объявления
16.03.2014, 08:05     Задана строка, символы которой могут повторяться. Нужно удалить все символы строки с помощью наименьшего количества вычеркиваний
Ответ Создать тему
Опции темы

Текущее время: 01:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru