记录编号	161909	评测结果	AAAAAAAAAA
题目名称	[LOL2000] 回文词	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	1.015 s
提交时间	2015-05-11 15:22:30	内存使用	96.05 MiB

#include <cstdio>

using namespace std;

char line[5010],line_r[5010];
int n,LCS[5010][5010];

int main()
{
	freopen("palin.in","r",stdin);
	freopen("palin.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",line);
	for(int i=0;i<n;i++)
	    line_r[n-i-1]=line[i];
	for(int i=0;i<n;i++)
	{
	    for(int j=0;j<n;j++)
	    {
			if(line[i]==line_r[j])
			{
				if(i==0||j==0) LCS[i][j]=1;
				else LCS[i][j]=LCS[i-1][j-1]+1;
			}
			else
			{
				if(i==0&&j==0) LCS[i][j]=0;
				else if(i==0) LCS[i][j]=LCS[i][j-1];
				else if(j==0) LCS[i][j]=LCS[i-1][j];
				else if(LCS[i-1][j]>LCS[i][j-1]) LCS[i][j]=LCS[i-1][j];
				else LCS[i][j]=LCS[i][j-1];
			}
	    }
	}
	printf("%d",n-LCS[n-1][n-1]);
	return 0;
}