Задача 67: Электронная почта (XIII Всеукраинская олимпиада по
информатике)
Пользователь сети Интернет подписан на
несколько разных списков рассылки, которые высылают ему по
электронной почте сообщения на определенные темы. Для удобства
пользователь создал себе набор папок, каждая из которых
соответствует одной из тем. Перед тем, как читать сообщения он
копирует их в соответствующую папку.
Почтовая программа, установленная на компьютере пользователя,
позволяет за одну "операцию" переносить из "списка новых сообщений"
в соответствующую папку:
- Одно сообщение из любого места списка
- Несколько сообщений, идущих в списке подряд, и относящихся к одной
теме
Переносить можно не обязательно начиная с начала "списка новых
сообщений". Пользователю необходимо перенести все новые сообщения в
соответствующие им папки за наименьшее количество операций.
Пример. Пусть пользователь подписан на рассылки анекдотов,
веселых историй, спортивных новостей и прогноза погоды. Пусть
"список новых сообщений" при некотором вхождении в почтовую
программу имел следующий вид: (Анекдоты, Спортивные новости, Прогноз
погоды, Спортивные новости, Веселые истории, Веселые истории,
Спортивные новости)
Список
папок Список новых сообщений
1 Анекдоты 1 Анекдоты
2 Веселые истории 3 Спортивные новости
3 Спортивные новости 4 Прогноз погоды
4 Прогноз погоды 3 Спортивные новости
2 Веселые истории
2 Веселые истории
3 Спортивные новости
Переносить
сообщения в папки он может следующим образом: сначала два сообщения
на тему "Веселые истории". Тогда он получит следующий список:
(Анекдоты, Спортивные новости, Прогноз погоды, Спортивные новости,
Спортивные новости). Потом перенести сообщения о прогнозе погоды,
после этого "Анекдоты", а потом, одновременно, все три сообщения о
спортивных новостях. На это он потратит 4 "операции".
Задание: Напишите программу EMAIL которая будет вычислять
минимальное количество "операций", с помощью которых можно перенести
все новые сообщения в папки. Для удобства каждой теме присваивается
номер.
Входные данные: Единственная строчка входного файла EMAIL.DAT
содержит число N (0 < N < 200), отвечающее количеству новых
сообщений и N целых чисел, которые соответствуют сообщениям, и
являются номерами тем, которым эти сообщения принадлежат.
Пример входных данных
7 1 3 4 3 2 2 3
Выходные данные. В первой строке выходного файла EMAIL.SOL
должно находиться минимальное число операций для данных, приведенных
во входном файле.
Пример выходных данных
4
Решение:
Итак, мы можем переносить несколько стоящих подряд сообщений за одно
действие. Это единственное, что может уменьшить общее количество
операций. Этим обстоятельством можно воспользоваться сразу при вводе
данных. Например, если мы встречаем сообщение на ту же тему что и
предыдущее, то не записываем его в массив. Технически это
реализуется с помощью цикла while, который рабоет до тех пор, пока
счетчик не достигнет значения, равного количеству сообщений. Если
нам встретилось сообщение, такое же, как предыдущее, то уменьшим
счетчик и количество сообщений на 1 (в итоге счетчик останется
неизмененным).
Теперь нам следует создать массив указателей на следующий элемент с
таким же номером. Каждый элемент должен ссылаться на такой же
элемент, стоящий справа от него, или содержать 0, если такого
элемента справа не существует.
Теперь начинается настоящая хитрость: эта задача решается методом
динамического программирования очень красиво, так красиво, что я еще
никогда не видел такого красивого решения этим часто используемым
способом. Заведем массив размером 200*200. Координатой по
горизонтали пусть будет номер левого элемента, а по вертикали -
правого. В ячейке массива будет храниться значение, сколько операций
необходимо осуществить, чтобы перетащить все сообщения от левого до
правого.
Как же заполнять этот массив? Логично, что для переноски одного
сообщения необходима ровно одна операция, т.е. главная диагональ
будет заполнена 1. Также мы знаем, что в силу особенностей ввода
информации у нас не может стоять подряд два сообщения с одной
тематикой, т.е. на перетаскивание двух подряд идущих сообщений нам
потребуется две операции.
А вот теперь самое интересное.
Если сообщений больше чем два, то следует рассматривать все гораздо
хитрее. Допустим, что оказалось так, что правое и левое сообщение
имеют одну и ту же тему, тогда:
Значение массива A[l, r] (здесь A - динамически подсчитываемый
массив, l и r - левая и правая границы) равно A[l + 1, r - 1] + 1,
т.е. мы можем растащить все сообщения между ними и они станут рядом
и вытащатся за одну операцию! Но может оказаться, что мы можем
растащить A[l, r] еще быстрее. Обратим внимание на наш массив
указателей на следующий аналогичный элемент NEXT. А что если между
этими одинаковыми элементами есть еще такие же (т.е. NEXT[l] <> R)?
Тогда найдем все элементы x = NEXT[x] (первоначально x = l), пока x
нее станет равно r. Тогда есть два варианта: если A[l, r] < A[l, x -
1] + A[x, r], то A[l, r] := A[l, x - 1] + A[x, r], т.е. может быть
нам выгоднее растащить группу от x до r (элементы с номерами x и r
равны, количество операций уже посчитано). Еще есть вариант, что
нужно растащить группу, как две группы: от l до x и от x + 1 до r
(значения также посчитаны). Мы будем изменять x, пока x не станет
равно r.
Теперь рассмотри вариант, если сообщения с номерами l и r имеют
разные темы. Растаскивание такого сообщения можно представить как A[l,
r] = min(A[l + 1, r], A[l, r - 1]) + 1, т.е. мы перетаскиваем
соседнюю группу сообщений и, затем, отдельно сообщение, которое в
эту группу не входит. Но в промежутке от l до r могут встретиться
сообщения, с такой же темой как у l. Это мы можем использовать. x =
NEXT[x], первоначально x = l. Условие выхода из цикла - если NEXT[x]
= 0, т.е. больше таких элементов не встречается, или NEXT[x] > r,
т.е. эти элементы больше не встречаются на интервале [l, r]. A[l, r]
= min(A[l, r], A[l + 1, x - 1] + A[x, r]) для каждого x. Т.е. мы
пытаемся из группы, например 3, 4, 2, 3, 6, 7 вытащить сначала
элементы 3, 4, 2, 3, а затем, отдельно, 6 и 7.
Технически это реализуется так: сначала заполняется главная
диагональ массива A[l, l] единицами, затем A[l, l + 1] = 2 (два
подряд разных сообщения), а затем запускается процедура
динамического подсчета с параметрами (1, 3), (2, 4), (3, 5), ...,
(1, 4), т.е. сначала проходяться все интервалы длиной 3, затем 4 и
т.п. Окончательным ответом будет значение в ячейке A[1, n], т.е.
левая граница 1, а правая - количество сообщений.
Далее
ð
