1002. Телефонные номера (ДП) [acm.timus.ru]

[Условие]

Основная идея:
Всю задачу можно разделить на 3 этапа:
1) Хранение данных
Каждое слово из словаря необходимо хранить как в цифровом, так и в буквенном варианте. Для слова “our” цифровое представление будет равно “087”. При этом необходимо иметь связь между между обоими представлениями для получения ответа. Один из вариантов хранения такого представления можно описать в виде структуры, а весь словарь в виде массива элементов таких структур:

1. struct word
2. {
3.   string str;      // буквенное представление
4.   string digits;   // цифровое представление
5. };
6. vector<word> dict; // словарь

По условию задачи длина каждого слова не превышает 50 символов. Тогда, вся структура word будет иметь размер в худшем случае 2*50=100 байт. Забегая вперед отметим, что по ходу решения нужно будет хранить словарь в отсортированном виде. При сортировке самая тяжеловесная операция – это обмен двух элементов местами. Поэтому есть предложение модифицировать нашу структуру для ускорения этой операции. Будем хранить в структуре не всю строчку в буквенном представлении, а только указатель на него.

1. struct word
2. {
3.   string digits;
4.   int id;
5.   word(){}
6.   word(string Digits, int Id)
7.   {
8.     digits = Digits;
9.     id = Id;
10.   }
11. };
12. vector<string> hash;
13. vector<word> dict;

Строковое представление слова храним в массиве hash, а в качестве id(указатель на строковое представления) храним индекс в массиве hash. При таком раскладе сортировка массива dict будет проходить быстрее, но в памяти будет храниться лишние 4 * N байт, где N – количество слов в dict.

2) Динамическое программирование
Для получения ответа заведем два массива last и amount, при этом:
last[i] – это номер слова из словаря, на которое заканчивается оптимальная комбинация слов при составлении начала исходного номера, начиная от 0-ого символа и заканчивая i-ым. (по умолчанию -1)
amount[i] – это количество слов в оптимальной комбинации, заканчивающейся i-ым символом. (по умолчанию infinity)
Наша задача последовательно заполнить массивы last и amount. При этом если последний элемент массива last равен –1, то можно с уверенностью сказать, что исходный номер нельзя представить в виде комбинации слов из словаря.
Детали реализации см. исходник (функция findAnswer)

3) Получение ответа
Рассмотрим массивы last и amount для первого теста:

index  = {  0,  1,  2,  3,  4,  5,  6,  7,  8,  9}
last   = { -1, -1, -1,  3, -1,  0,  2, -1, -1,  4}
amount = {inf,inf,inf,  1,inf,  2,  1,inf,inf,  2}

Ответ формируем с конца.
3.1) Текущий индекс = 9. Последнее слово ответа имеет id = 4. Это слово “our”.
3.2) id предыдущего слова хранится левее на расстоянии длины текущего слова по индексу 6, т.е. id = 2. Это слово “reality”.
3.3) После выполнения шага 3.2) мы находимся в –1 индексе. Это сигнализирует о том, что ответ найден. Выводим его без лишних пробелов

[Исходный код]