记录编号	3675	评测结果	AAAAAAWAWA
题目名称	[LOL2000] 回文词	最终得分	80
用户昵称	BYVoid	是否通过	未通过
代码语言	C++	运行时间	0.514 s
提交时间	2008-10-08 22:26:19	内存使用	0.28 MiB

#include <iostream>
#define MAX 5001
using namespace std;

char S[MAX];
int F[MAX];
int Ans,N;

void init()
{
	int i;
	freopen("palin.in","r",stdin);
	freopen("palin.out","w",stdout);
	scanf("%d\n%s",&N,S+1);
}

void dynamic()
{
	int A,i,j,W,p,q;
	Ans=N;
	for (i=1;i<=N;i++)
	{
		q=0;
		W=N-i < N/2 ? N-i : N/2;
		for (j=1;j<=W;j++) 
		{
			p=q;
			q=F[j];
			if (S[i]==S[N-j+1]) 
			{
				if (p+1>F[j])
					F[j]=p+1;
			}
			else
			{
				if (F[j-1]>F[j])
					F[j]=F[j-1];
			}
			if (i+j>=N-1)
			{
				A=N-F[j]*2-(N-i-j);
				if (Ans>A)
					Ans=A;
			}
		}
	}
}

int main()
{
	init();
	dynamic();
	cout << Ans << endl;
	return 0;
}