分析：我们可以轻易的想到：回文串后半段逆序排列，与前半段是相等的。于是首先将整个字符串倒置，我们看得出，在倒置串与原串同时取出一个子串，如果相等，再将其它不相等项在另一个串中同一位置补一个，两串即可构成回文。所以找出倒置串与原串的最长公共串（不一定连续），再用字符串长度减去它就是答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
string s,c;
int n,a[5001][5001],m;
int main()
{
memset(a,0,sizeof(a));
cin>>n;
getchar();
getline(cin,s);
c=s;
for(int i=0;i<=n/2-1;i++)swap(c[i],c[n-1-i]);
for(int i=0;i<=n-1;i++)
for(int j=0;j<=n-1;j++)
if(s[i]==c[j])a[i+1][j+1]=a[i][j]+1;
else a[i+1][j+1]=max(a[i+1][j],a[i][j+1]);
cout<<n-a[n][n];
return 0;
}

看了一下，题解前篇一律地选择了将自身反序拼接到尾部，然后求公共字串，所以写个自己的动态转移方程
dp[head][tail] 前head个字符，与后tail个字符满足回文条件
dp[head][tail] = min(
dp[head-1][tail]+1,
dp[head][tail-1]+1,
dp[head-1]tail-1
)
dp[0][0] = 0，边界以外的值为正无穷

最后找到dp[k][n-k](第一次提交，没有注意这种情况，错了5组数据，搞得我的很尴尬……这种模式极为没有最中间为两个元素的对称模式） dp[k]n-k-1中的最小值则是答案

#1 Accepted 35ms 95.59 MiB
#2 Accepted 35ms 95.691 MiB
#3 Accepted 35ms 95.66 MiB
#4 Accepted 34ms 95.691 MiB
#5 Accepted 37ms 95.645 MiB
#6 Accepted 38ms 95.621 MiB
#7 Accepted 36ms 95.711 MiB
#8 Accepted 34ms 95.652 MiB
#9 Accepted 83ms 95.652 MiB
#10 Accepted 96ms 95.695 MiB
#11 Accepted 93ms 95.664 MiB
#12 Accepted 92ms 95.605 MiB
#13 Accepted 35ms 95.676 MiB
#14 Accepted 39ms 95.688 MiB
#15 Accepted 148ms 95.605 MiB
#16 Accepted 97ms 95.633 MiB
#17 Accepted 94ms 95.695 MiB

CPP程序，每组数据时间都比较平均但都不是0，推测为memset一个5000*5000的数组太耗时间了，改成指针估计就多数都是0秒了

var
i,j,n,m:longint;
s,s1:ansistring;
a:array[0..5000,0..5000] of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
readln(n);
readln(s);
fillchar(a,sizeof(a),0);

for i:=n downto 1 do
s1:=s1+s[i];
for i:=1 to n do
for j:=1 to n do
if s[i]=s1[j] then a[i,j]:=a[i-1,j-1]+1
else a[i,j]:=max(a[i-1,j],a[i,j-1]);
writeln(n-a[n,n]);
end.

f[i,j]表示a[1..i]这一段与a[n..i+1]这一段的最大公共子序列
var
i,j,k,m,n,ans:longint;
a:array[0..5100]of char;
f:array[0..5001,0..5001]of integer;
function max(a,b:integer):integer;
begin
if a>b then exit(a);exit(b);
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n-1 do
for j:=n downto i+1 do
if a[i]=a[j] then
f[i,j]:=f[i-1,j+1]+1
else
f[i,j]:=max(f[i-1,j],f[i,j+1]);
ans:=maxlongint;
for i:=1 to n-1 do
begin
if ans>n-2*f[i,i+1] then
ans:=n-2*f[i,i+1];
if ans>n-2*f[i,i+2]-1 then
ans:=n-2*f[i,i+2]-1;
end;
writeln(ans);
end.

var n,i,j,k:longint;

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

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

　　ss:char;

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

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

begin

　　 f:=f;

　　 if f

【转述】给一个类回文词的字符串，其中有些可以去掉的字符使它 成为一个真正的回文词，求出他们的个数。

【分析】本题是一道典型的合并类动态规划，为什么说是合并呢，设序列V，s[i]=到s[j]区间的最优值实际上是由一个回文词扩展而来，在扩展的过程中也考虑加入了不符合回文词的字符如Ab3bd

s= 3 b3b Ab3b Ab3bd

ans= 0 0 1 2

也就是说我们可以已一个区间f（s串从ｉ到ｊ）来划分阶段，且它只能作用于f或f或f，各状态之间只存在扩展应用的关系，不存在互相影响，而且任何字串都可以写成上述的扩展形式由此推方程

如果 s[i]=s[j] f=f 可以扩展成新的回文词

如果 s[i]s[j] f=min{f,f} 原回文词无法扩展，只能先加入不合法的字符

主程序：

for l:=2 to n do

begin

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

begin

j:=i+l-1;

f:=min(f,f)+1;

if s[i]=s[j]

then f:=min(f,f);

end;

end;

Ac标程见http://zhurui250.blog.163.com/blog/static/137270520201021011229583/我的博客：http://zhurui250.blog.163.com/

var

st1,st2:ansistring;

i,j,k,ans,n:longint;

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

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

begin

if a>b then exit(a)

else exit(b);

end;

begin

readln(n);

readln(st1);

st2:='';

for i:=1 to n do st2:=st1[i]+st2;

for i:=1 to n do

begin

for j:=1 to n do

if st1[i]=st2[j] then f[1,j]:=f[0,j-1]+1

else f[1,j]:=max(f[0,j],f[1,j-1]);

for j:=1 to n do

f[0,j]:=f[1,j];

end;

for i:=1 to n do

if f[1,i]>ans then ans:=f[1,i];

ans:=n-ans;

writeln(ans);

end.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

初始化没清零……值两组呢

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：运行超时...

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

├ 测试数据 11：运行超时...

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

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

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

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

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

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

悲剧的记忆化...

求最长公共子串再用总长度减（用short）

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f:=min(f,f)+1

第一次：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第二次：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

求秒杀程序

谁有方法Q我（1024849527）！谢谢！

一定要哦！！！！

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

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

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

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

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

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

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

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

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

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

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

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

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

├ 测试数据 14：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 16：答案错误...　├ 标准行输出

　├ 错误行输出

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

program p1327;

type arr=array[0..5000] of integer;

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

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

a,b:arr;

min,n,b1,b2:integer;

procedure init;

var i:integer;

begin

readln(n);

for i:=1 to n do

begin

read(ch[i]);

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

end;

end;

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

begin

if a>b then smaller:=b

else smaller:=a;

end;

procedure doit;

var x,i,j:integer;

begin

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

min:=n;

for i:=1 to n do

begin

b2:=0;

for j:=1 to smaller(n-i,n div 2) 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.

书上程序有问题！94分！

var n,i,j:longint;

s1,s2:ansistring;

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

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

begin

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

end;

begin

readln(n);

readln(s1);

for i:=1 to n do

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

fillchar(f,sizeof(f),0);

for i:=1 to n do

for j:=1 to n do

if s1[i]=s2[j] then f[i mod 2,j]:=f[(i-1) mod 2,j-1]+1

else f[i mod 2,j]:=max(f[(i-1) mod 2,j],f[i mod 2,j-1]);

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

end.

dp吧

竟然错了3次，最后发现变量错了......

orz......

两点注意：

1.千万不要写记忆化！！！

2.千万不要用integer(才怪！)

知道DP方程后，程序很EASY，才十多行，但这个题的思想才是最重要的。体现了字符串的三种经典操作：A加B不加，B加A不加，AB都不加。

var n,i,j,k:longint;

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

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

ss:char;

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

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

begin

f:=f;

if f

f表示第i个字符到第j个字符变为回文词的最小插入数。

f=min(f+1,f+1,f+ord(a[i]a[j])*2

这样，时间复杂度O(n^2)，空间复杂度也是。时间不会爆，空间会爆。

就再用滚动数组即可优化成空间复杂度为O(2n)。

-.-发现我习惯性把数组定义为longint型，则爆了空间。用integer就不会了。

├ 测试数据 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：运行超时...

结果显示 Accepted 0 0

var

st,sr:array[1..5000]of char;

i,n,j,k:integer;

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

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

begin

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

end;

Begin

readln(n);k:=n;

for i:=1 to n do

begin

read(st[i]);

sr[k]:=st[i];

dec(k);

end;

for j:=1 to n do

for i:=1 to n do

begin

if st[j]=sr[i] then map:=map+1

else map:=max(map,map);

end;

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

End.

为什么 我总是遇到sunny？ 哎RP不好！！！