Тема: ДП
Вот задача.Решаю двумерным массивом,выходит Memory limit. Может кто знает решение получше? Предлагали перебирать все центры возможных "почти палиндромов". Но как это сделать?
Re: ДП
Сдал только что - перебирал все центры и бежал в две стороны - и если нашли несовпадение, то уменьшаем количество разрешенных замен на 1 (и так пока это количество > 0), походу дела наращиваем ответ. Пробежки таких делать надо две - одну для случая палиндромов нечетной длины, одну - для четной.
реализация на всякий пожарный:
#include <iostream>
#include <string>
using namespace std;
string s;
int n, k;
int main()
{
cin >> n >> k;
cin >> s;
int cnt = 0;
for (int c = 0; c < n; c++) {
int i = c, j = c, allowed = k;
while (i >= 0 && j < n && (s[i] == s[j] || allowed > 0)) {
if (s[i] != s[j])
--allowed;
--i, ++j, ++cnt;
}
}
for (int c = 0; c < n; c++) {
int i = c, j = c + 1, allowed = k;
while (i >= 0 && j < n && (s[i] == s[j] || allowed > 0)) {
if (s[i] != s[j])
--allowed;
--i, ++j, ++cnt;
}
}
cout << cnt << "\n";
}Re: ДП
А где тут динамика?
Re: ДП
Походу задача совсем не на динамику?
Re: ДП
А вот эту я реши l,r динамикой но почему-то 11 тест WA.
Вот код:
type aaa=record
s:string;
d:longint;
end;
var
d:array[-1..110,-1..110] of aaa;
n,i,j:longint;
s:string;
function m(q,w:char):boolean;
begin
m:=((q='[')and(w=']'))or((q='{')and(w='}'))or((q='(')and(w=')'));
end;
function f(l,r:longint):aaa;
var k:longint; min,t1,t2:aaa;
begin
if (l<r)and(d[l,r].d=-1) then
begin
if m(s[l],s[r]) then begin t1:=f(l+1,r-1); d[l,r].d:=t1.d; d[l,r].s:=s[l]+t1.s+s[r]; end else
begin
min.d:=maxlongint;
for k:=l to r-1 do
begin
t1:=f(l,k); t2:=f(k+1,r);
if min.d>t1.d+t2.d then begin min.d:=t1.d+t2.d; min.s:=t1.s+t2.s; end;
end;
d[l,r]:=min;
end;
end;
f:=d[l,r];
end;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(s); n:=length(s);
for i:=1 to n do
begin
for j:=-1 to i do begin d[i,j].d:=0; d[i,j].s:=''; end;
for j:=i+1 to n do begin d[i,j].d:=-1; d[i,j].s:=''; end;
d[i,i].d:=1;
end;
write(f(1,n).s);
close(input); close(output);
end.Где у меня ошибка?