Question

Một người sử dụng INTERNET đặt yêu cầu nhận thông tin về một số chủ đề khác nhau từ một số địa chỉ truy nhập. Chủ của các địa chỉ truy nhập này sẽ gửi thông tin yêu cầu vào hòm thư của người đặt hàng. Mỗi thông tin nhận được từ địa chỉ truy nhập sẽ được ghi vào một danh mục trong máy của người sử dụng dưới dạng một file mà để ngắn gọn ta sẽ gọi là một thông báo. Để thuận tiện cho việc tra cứu, người sử dụng quyết định xây dựng các cặp tài liệu, mỗi cặp chứa thông tin về cùng một chủ đề. Trước khi đọc tài liệu người sử dụng sẽ sao chép chúng từ danh mục các thông báo nhận được vào các cặp tương ứng.

Chương trình hộp thư điện tử gắn trên máy của người sử dụng cho phép sau "một thao tác" chuyển từ danh mục thông báo vào cặp tài liệu:

• Một thông báo từ danh mục hoặc
• Một dãy các thông báo liên tiếp nhau trong danh mục về cùng một chủ đề

Việc chuyển thông báo không nhất thiết phải bắt đầu từ đầu danh mục.

Cần tìm cách chuyển các thông báo trong danh mục vào các cặp tương ứng đòi hỏi số thao tác phải thực hiện là ít nhất.

Ví dụ: Giả sử người sử dụng muốn thu thập thông tin về các chủ đề A, B, C, D. Giả sử danh mục các thông báo nhận được theo trình tự thuộc về các chủ đề (A, C, D, C, B, B, C). Việc di chuyển vào cặp tài liệu có thể thực hiện như sau: Đầu tiên di chuyển hai thông báo B, khi đó danh mục còn lại là (A, C, D, C, C). Tiếp theo thực hiện việc di chuyển thông báo D, rồi thông báo A và cuối cùng di chuyển nốt 3 thông báo C liền nhau. Cách làm này đòi hỏi 4 thao tác.

Dữ liệu: Vào từ file văn bản EMAIL.INP gồm một dòng chứa số nguyên dương N (0

Kết quả: Ghi ra file EMAIL.OUT số thao tác ít nhất cần thực hiện.

Ví dụ:

EMAIL.INP	EMAIL.OUT
7 1 3 4 3 2 2 3	4

Answer 1

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

uses crt;

const
   tfi                  =       'EMAIL.INP';
   tfo                  =       'EMAIL.OUT';
   maxN                 =       50;
   NN                   =       50;

type
   mang=array[1..maxN] of byte;

var
  fi,fo: text;
  N: integer;
  a: array[1..maxN] of byte;
  S: integer;
  b: array[1..maxN,1..maxN] of ^mang;

procedure Docdl;
var i: integer;
begin
   assign(fi,tfi); reset(fi);
   read(fi,N);
   for i:=1 to N do read(fi,a[i]);
   close(fi);
end;

function Tinh(u,v,k: integer): byte;
var T: byte;
    p,q,tt,tp,tc: integer;
begin
   if b[u,v]^[k]<>255 then
      begin
         Tinh:=b[u,v]^[k];
         exit;
      end;
   if u=v then
      begin
         b[u,v]^[k]:=1;
         Tinh:=1;
         exit;
      end;
   if k=u then
      begin
         T:=255;
         for q:=u+1 to v do
            begin
               tp:=Tinh(u+1,v,q);
               if a[q]<>a[u] then tp:=tp+1;
               if tp             end;
         b[u,v]^[k]:=T;
         Tinh:=T;
         exit;
      end;
   if k=v then
      begin
         T:=255;
         for p:=u to v-1 do
            begin
               tt:=Tinh(u,v-1,p);
               if a[p]<>a[v] then tt:=tt+1;
               if tt             end;
         b[u,v]^[k]:=T;
         Tinh:=T;
         exit;
      end;
   T:=255;
   for p:=u to k-1 do
      for q:=k+1 to v do
         begin
            tt:=Tinh(u,k-1,p);
            tp:=Tinh(k+1,v,q);
            if (a[p]=a[k]) and (a[k]=a[q]) then tc:=tt+tp-1 else
            if (a[p]=a[k]) and (a[k]<>a[q]) then tc:=tt+tp else
            if (a[p]<>a[k]) and (a[k]=a[q]) then tc:=tt+tp else
            tc:=tt+tp+1;
            if tc          end;
   b[u,v]^[k]:=T;
   Tinh:=T;
end;

procedure Solve;
var k,T: integer;
begin
   S:=maxInt;
   for k:=1 to N do
       begin
          T:=Tinh(1,n,k);
          if T        end;
end;

procedure Inkq;
begin
   assign(fo,tfo); rewrite(fo);
   writeln(fo,S);
   close(fo);
end;

procedure CapPhat;
var i,j,k: integer;
begin
   for i:=1 to NN do
      for j:=1 to NN do
         begin
            new(b[i,j]);
            for k:=1 to NN do b[i,j]^[k]:=255;
         end;
end;

BEGIN
   CapPhat;
   Docdl;
   Solve;
   Inkq;
END.