Палиндромы

[Snake08]

Палиндромы 1!
Задана строка, которая составляется из малых латинских букв. Разрешается удалять из строки определенные буквы. Сколькими разными образами можно при этом получить палиндром?
Входные данные: заданная строка находится в файле palindrome1.dat, длина его не превышает 30 символов
Исходные данные: в первую строку файла palindrome1.sol надо вывести искомое количество образов получения палиндрому
Пример входных и исходных данных:
palindrome1.dat
aab
palindrome1.sol
4
Объяснение: палиндром можно получить, удалив символы 1) 1 і 2; 2) 1 і 3; 3) 2 і 3; 4) 3!
Палиндромы 2!
Задана строка, которая составляется из малых латинских букв. Нужно разбить его на минимальное возможное количество палиндромов.
Входные данные: заданная строка находится в файле palindrome2.dat, длина не превышает 2000 символов
Исходные данные: в первую строку файла palindrome2.sol надо вывести минимальное количество палиндромов, на которые можно разбить строку
Пример входных и исходных данных:
palindrome2.dat
abbacbb
palindrome2.sol
3
Объяснение: abbacbb = abba + c + bb

[Min]

Вот первая. Динамика рулит)))

var a:array[0..30,0..30] of longint;
    i,j,n,x,y:byte;
    s:string;
begin
 readln(s);
 n:=length(s);
 for i:=1 to n do
  a[i,i]:=1;

 for j:=2 to n do
  for i:=1 to n-j+1 do
   if(s[i]=s[i+j-1]) then a[i+j-1,i]:=a[i+j-2,i]+a[i+j-1,i+1]+1
   else a[i+j-1,i]:=a[i+j-2,i]+a[i+j-1,i+1]-a[i+j-2,i+1];

 writeln(a[n,1]);
 readln;
end.

[Snake08]

Спасибо Min за 1 задачку большое человечиское! А попробуй зделать еще й 2!Пожалуста!

[Min]

не уверен на 100%, но кажись работает)))))

var a:array[1..2000,1..2000] of byte;

function f(x,y:byte):byte;
var i:byte;
    minA,q:byte;
begin
 minA:=255;
 for i:=y to x-1 do
  begin
   q:=a[i,y]+a[x,i+1];
   if q<MinA then MinA:=q;
  end;
 f:=MinA;
end;

function min(x1,x2:byte):byte;
begin
 if(x1>x2) then min:=x2
  else min:=x1;
end;

function max(x1,x2:byte):byte;
begin
 if(x1>x2) then max:=x1
  else max:=x2;
end;

var i,j,n:byte;
    s:string;
begin
 readln(s);
 n:=length(s);
 for i:=1 to n do
  a[i,i]:=1;
 for i:=2 to n do
  if(s[i]=s[i-1]) then a[i,i-1]:=1 else a[i,i-1]:=2;

 for i:=3 to n do
  for j:=n-i downto 0 do
   if(s[i+j]<>s[j+1]) then a[i+j,j+1]:=f(i+j,j+1)
    else a[i+j,j+1]:=min(a[i+j-1,j+2],max(a[i+j-1,j+1],a[i+j,j+2]));

 writeln(a[n,1]);
 readln;
end.

[Min]

только поменяй byte на integer для больших чисел

[Snake08]

""var a:array[1..2000,1..2000] of byte;""
Вот ета строка не работает до 2000 только до 200, и когда меняю на integer или longint то выбивает ошибку што очень большая структура!
Подскажите што можно зделать!

[Min]

дэээ..... чет не подумал...... как вариант могу предложить использовать вместо массива 4х-направленный список..... есть ещё одна мысль, но это долго объяснять.....