记录编号	3672	评测结果	ATTATAATAA
题目名称	[LOL2000] 回文词	最终得分	70
用户昵称	zqzas	是否通过	未通过
代码语言	C++	运行时间	6.241 s
提交时间	2008-10-08 22:25:39	内存使用	48.14 MiB

#include <iostream>

#define MAXN 5010

using namespace std;

short ans,len,f[MAXN][MAXN];
char data[MAXN];

void search(int a,int b)
{
	if (a==b || (a+1==b && data[a]==data[b]))
	{
		f[a][b]=0;
		return;
	}
	f[a][b]=b-a+1;
	//st 0
	if (data[a]==data[b])
	{
		if (f[a+1][b-1]==-1)
			search(a+1,b-1);
		if (f[a+1][b-1]<f[a][b])
			f[a][b]=f[a+1][b-1];
	}
	//st 1
	if (f[a+1][b]==-1)
		search(a+1,b);
	if (f[a+1][b]+1<f[a][b])
		f[a][b]=f[a+1][b]+1;
	//st 2
	if (f[a][b-1]==-1)
		search(a,b-1);
	if (f[a][b-1]+1<f[a][b])
		f[a][b]=f[a][b-1]+1;
}

void run()
{
	search(0,len-1);
	ans=f[0][len-1];
}

void ini()
{
	scanf("%d\n",&len);
	scanf("%s",&data);
	for (int i=0;i<=len+1;i++)
		for (int j=0;j<=len+1;j++)
			f[i][j]=-1;
}

int main()
{
	freopen("palin.in","r",stdin);
	freopen("palin.out","w",stdout);
	ini();
	run();
	cout<<ans;
	return 0;
}