Скачать программы    Все программы автора

ЭЛЕКТРОННАЯ ПОЧТА

Пользователь сети Интернет подписан на несколько разных списков рассылки, которые высылают ему по электронной почте сообщения на определенные темы. Для удобства пользователь создал себе набор папок, каждая из которых соответствует одной из тем. Перед тем, как читать сообщения он копирует их в соответствующую папку.

Почтовая программа, установленная на компьютере пользователя, позволяет за одну “операцию” переносить из “списка новых сообщений” в соответствующую папку:

Одно сообщение из любого места списка.

Несколько сообщений, идущих в списке подряд, и относящихся к одной теме.

Переносить можно не обязательно начиная с начала “списка новых сообщений ”. Пользователю необходимо перенести все новые сообщения в соответствующие им папки за наименьшее количество операций.

Пример. Пусть пользователь подписан на рассылки анекдотов, веселых историй, спортивных новостей и прогноза погоды. Пусть “список новых сообщений” при некотором вхождении в почтовую программу имел следующий вид: (Анекдоты, Спортивные новости, Прогноз погоды, Спортивные новости, Веселые истории, Веселые истории, Спортивные новости)

Переносить сообщения в папки он может следующим образом: сначала два сообщения на тему “Веселые истории”. Тогда он получит следующий список: (Анекдоты, Спортивные новости, Прогноз погоды, Спортивные новости, Спортивные новости). Потом перенести сообщения о прогнозе погоды, после этого “Анекдоты”, а потом, одновременно, все три сообщения о спортивных новостях. На это он потратит 4 “операции”.

Задание Напишите программу EMAIL которая будет вычислять минимальное количество “операций”, с помощью которых можно перенести все новые сообщения в папки. Для удобства каждой теме присваивается номер.

Входные данные Единственная строчка входного файла EMAIL.DAT содержит число N (0<N<200), отвечающее количеству новых сообщений и N целых чисел, которые соответствуют сообщениям, и являются номерами тем, которым эти сообщения принадлежат.

Пример входных данных

7 1 3 4 3 2 2 3

Выходные данные В первой строке выходного файла EMAIL.SOL должно находиться минимальное число операций для данных, приведенных во входном файле.

Пример выходных данных

4

{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}

{$M 16384,0,655360}

const

FileIn = 'email.dat';

FileOut = 'email.sol';

MaxN = 200;

var

N : integer;

B : array[1..MaxN] of integer; {Input array}

A : array[1..MaxN, 1..MaxN] of byte; {Dynamic matrix}

Next : array[1..MaxN] of integer; {Next and previous element}

procedure Init;

var

F : Text;

i,j : integer;

begin

{Get input data B[]}

Assign(F, FileIn);

Reset(F);

Read(F,N);

{ for i:=1 to N do

Read(F, B[i]);}

i:=0;

while i<N do

begin

Inc(i);

Read(F, B[i]);

if i<>1 then

if B[i]=B[i-1] then

begin Dec(i); Dec(n); end;

end;

Close(F);

{Generation of Next[] arrays}

FillChar(Next, SizeOf(Next),0);

for i:=1 to n do

begin

j:=i+1;

while (j<=n)and(B[i]<>B[j]) do Inc(j);

if j<=n then Next[i]:=j;

end;

{Initialisation of matrix A[]}

FillChar(A, SizeOf(A), 0);

for i:=1 to n do a[i,i]:=1;

end;

function min(a,b : integer):integer;

begin if a<b then min:=a else min:=b end;

procedure Run;

var

l,m,i,j,s : integer;

begin

{Building of matrix A[]}

for l:=2 to n do

for m:=1 to n-l+1 do

begin

i:=m; j:=l+m-1;

if B[i]<>B[j] then

begin{There is two diferents themas}

A[i,j]:=min(A[i+1,j], A[i,j-1])+1;

s:=i;

while (Next[s]<>0)and(Next[s]<j) do

begin

s:=Next[s];

A[i,j]:=min(A[i,j], A[i+1,s-1]+A[s,j]);

end;

end else

begin {There is two same themas}

A[i,j]:=A[i+1,j-1]+1; {inner}

s:=i;

while Next[s]<>j do

begin

s:=Next[s];

A[i,j]:=min(A[i,j], A[i+1,s-1]+A[s,j]);

end;

end;

end;

end;

procedure Done;

var

F : Text;

i,j : integer; {*************}

begin

{Printing results}

Assign(F, FileOut);

Rewrite(F);

WriteLn(F,A[1,n]);

{***********}

{ for i:=1 to n do

begin

for j:=1 to n do

Write(F, A[i,j]:3);

WriteLn(F);

end;}

{***********}

Close(F);

end;

begin

Init;

Run;

Done;

end.