For i:=1 to n do

f:=0;

For k:=2 to n do

For i:=1 to n-k+1 do

if ch[i]=ch then f:=f

else f:=Min(f,f)+1;

writeln(f[1,n]);

水题，二十几行搞定

program poj1159;

var s1,s2:array[0..5000] of char;

f:array[0..5000,0..5000] of integer;

n,i,j:integer;

function max(a,b,c:integer):integer;

begin

if b>a then a:=b;

if c>a then a:=c;

exit(a);

end;

begin

readln(n);

for i:=1 to n do

begin

read(s1[i]);

s2[n-i+1]:=s1[i];

end;

for i:=1 to n do

for j:=1 to n do

begin

if s1[i]=s2[j] then f:=f+1;

f:=max(f,f,f);

end;

writeln(n-f[n,n]);

end.

f[j,i]为j到i的最优值

f[j,i]=f[j+1,i-1] (a[j]=a[i])

=min(f[j,i-1],f[j+1,i])+1; (a[j]a[i])

原来是开5000*5000的longint

结果

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：内存溢出...

├ 测试数据 10：内存溢出...

├ 测试数据 11：内存溢出...

├ 测试数据 12：内存溢出...

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：内存溢出...

├ 测试数据 16：内存溢出...

├ 测试数据 17：内存溢出...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：79 有效耗时：0ms

于是想到了滚动数组 可是懒得改了

于是改成了5000*5000的integer

结果就AC了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 197ms

├ 测试数据 11：答案正确... 166ms

├ 测试数据 12：答案正确... 166ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 291ms

├ 测试数据 16：答案正确... 181ms

├ 测试数据 17：答案正确... 181ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1363ms

还是有点慢 不过懒得优化了 O(∩_∩)O~ 偶是懒人一条

---|---|---|---|---|---|---|---|---|---|---|晒程序啊---|---|---|---|---|---|---|---|--

var i,j,n:longint;

ch:char;

a,b:array[0..5005] of integer;

f:array[0..5002,0..5002]of integer;

begin

readln(n);

for i:=1 to n do begin

read(ch); a[i]:=ord(ch);

b[n-i+1]:=a[i];

end;

for i:=1 to n do

for j:=1 to n do begin

if a[i]=b[j] then f:=f+1;

if f

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 9ms

├ 测试数据 11：答案正确... 25ms

├ 测试数据 12：答案正确... 41ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 134ms

├ 测试数据 16：答案正确... 103ms

├ 测试数据 17：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：378ms

好慢啊！

Accepted 有效得分：100 有效耗时：1127ms

要用ansistring……心碎ing

为什么我某些点内存溢出，某些点0ms通过

郁闷。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 212ms

├ 测试数据 10：答案正确... 119ms

├ 测试数据 11：答案正确... 103ms

├ 测试数据 12：答案正确... 134ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 275ms

├ 测试数据 16：答案正确... 291ms

├ 测试数据 17：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1206ms

记录编号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1289554 Accepted 100 From 木子日匀－

　P1327 FPC Vivid Puppy 2009-7-2 21:48:30

R1289552 Unaccepted 9 From 木子日匀－

　P1327 FPC Vivid Puppy 2009-7-2 21:47:30

R1289550 Unaccepted 9 From 木子日匀－

　P1327 FPC Vivid Puppy 2009-7-2 21:46:12

R1289540 Unaccepted 9 From 木子日匀－

　P1327 FPC Vivid Puppy 2009-7-2 21:42:34

R1289536 Unaccepted 3 From 木子日匀－

　P1327 FPC Vivid Puppy 2009-7-2 21:41:26

R1289530 Unaccepted 0 From 木子日匀－

　P1327 FPC Vivid Puppy 2009-7-2 21:39:56

R1289523 Unaccepted 0 From 木子日匀－

　P1327 FPC Vivid Puppy 2009-7-2 21:38:39

R1289518 Unaccepted 0 From 木子日匀－

　P1327 FPC Vivid Puppy 2009-7-2 21:37:23

program ex;

var h1,m1,s1,ms1,h2,m2,s2,ms2:word;

ch,ch1:array[1..5000] of char;

a,b:array[0..5000] of longint;

min,n,b1,b2:longint;

procedure init;

var i:longint;

begin

readln(n);

for i:=1 to n do

begin

read(ch[i]);

ch1[n-i+1]:=ch[i];

end;

end;

procedure doit;

var x,i,j:longint;

begin

fillchar(a,sizeof(a),0);

min:=n;

for i:=1 to n do

begin

b2:=0;

for j:=1 to n-i do

begin

b1:=b2;

b2:=a[j];

if ch[i]=ch1[j] then

begin

if b1+1>a[j] then a[j]:=b1+1;

end

else if a[j-1]>a[j] then a[j]:=a[j-1];

if i+j>=n-1 then

begin

x:=n-a[j]*2-(n-i-j);

if min>x then min:=x;

end;

end;

end;

writeln(min);

end;

begin

init;

doit;

end.

一遍过了，高级本上有~~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 212ms

├ 测试数据 10：答案正确... 431ms

├ 测试数据 11：答案正确... 322ms

├ 测试数据 12：答案正确... 322ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 541ms

├ 测试数据 16：答案正确... 353ms

├ 测试数据 17：答案正确... 478ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2659ms

用滚动数组做的，节省了空间

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 25ms

├ 测试数据 12：答案正确... 25ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 134ms

├ 测试数据 16：答案正确... 134ms

├ 测试数据 17：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：400ms

简单的DP，注意加加减减的能省则省，时间复杂度是n*n。

数组开n*n的整型就过了，长整型过不了。

var i,j,n:integer;

a:array[1..5000] of char;

f:array[1..5000,0..4999] of integer;

begin

readln(n);

for i:=1 to n do begin

read(a[i]);

f:=0;

end;

for j:=1 to n-1 do

for i:=1 to n-j do

if a[i]=a then f:=f else

if f

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 508ms

├ 测试数据 10：答案正确... 259ms

├ 测试数据 11：答案正确... 415ms

├ 测试数据 12：答案正确... 399ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 540ms

├ 测试数据 16：答案正确... 571ms

├ 测试数据 17：答案正确... 274ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2966ms

这么简单的题目是ioi的？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 633ms

├ 测试数据 10：答案正确... 493ms

├ 测试数据 11：答案正确... 555ms

├ 测试数据 12：答案正确... 571ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 649ms

├ 测试数据 16：答案正确... 696ms

├ 测试数据 17：答案正确... 493ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4090ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 9ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

不容易啊

强烈鄙视Vag 6k 测评机

这么慢....

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 399ms

├ 测试数据 10：答案正确... 571ms

├ 测试数据 11：答案正确... 462ms

├ 测试数据 12：答案正确... 462ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 602ms

├ 测试数据 16：答案正确... 508ms

├ 测试数据 17：答案正确... 446ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3450ms

vag 6k 测的，就是慢啊。。。。。。

我是dp做的，先做一遍最长公共字串长度，就可以做了

囧~

第一次开5000*5000的LONGINT数组把内存超了....

改成INTEGER的就过了

可惜很慢...

更好的方法不会..

郁闷~

为啥看以前的大牛时间都这么长呢

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 9ms

├ 测试数据 12：答案正确... 9ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 72ms

├ 测试数据 16：答案正确... 88ms

├ 测试数据 17：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：250ms

我用的方法是Dp

Dp[x,l]:=Dp[x+1,l-2] | a[x]=a[x+l-1] & l>2

min(dp[x,l-1],dp[x+1,l-1])+1 |a[x]a[x+l-1]

0 | a[x]=a[x+l-1] & l

Program P1327;

var f:array[1..5000,1..5000]of longint;

var i,j,n,k,l:longint;

var s:string;

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

begin

if a>b then exit(b) else exit(a);

end;

begin

readln(n);

readln(s);

l:=length(s);

k:=l div 2;

f[k,k]:=0;

for i:=k-1 downto 1 do

for j:=k+1 to l do

begin

if s[i]=s[j] then f:=min(f,f);

if s[i]s[j] then f:=min(f,f)+1;

end;

writeln(f[1,n]);

end.

历史遗留问题啊。。今天大清理ING。。