记录编号	158488	评测结果	AAAAAAAAAA
题目名称	[LOL2000] 回文词	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	1.469 s
提交时间	2015-04-15 15:51:03	内存使用	0.49 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
char a[10000],b[10000];
int n;
long long opt[2][10000];
int main()
{
	freopen("palin.in","r",stdin);
	freopen("palin.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;++i)
	 cin>>a[i];
	for (int i=1;i<=n;++i)
	 b[i]=a[n-i+1];
	int k0=0;
	int k1=1;
	for (int i=1;i<=n;++i)
	 {
	 	memset(opt[k1],0,sizeof(opt[k1]));
	 	for (int j=1;j<=n;++j)
	 	{
	 		opt[k1][j]=max(opt[k0][j],opt[k1][j-1]);
	 		if (a[i]==b[j])
	 		 opt[k1][j]=max(opt[k1][j],opt[k0][j-1]+1);
	 	}
	 	int x=k0;
	 	k0=k1;
	 	k1=x;
	 }
	cout<<n-opt[k0][n];
	return 0;
}