#include<stdio.h>
#include<string.h>
	
int main()
{
    char a[5000],b[5000];
	int n,p[5000],q[5000],z[5000],i,j,k;
	scanf("%d%s",&n,a);
	for(j=0,i=n-1;i>=0;--i)
		b[j++]=a[i];
//	b[j]=0;     为什么加上这句就WA ? 去掉就AC。——明明b[n]是在后面的程序中没使用到的,郁闷了好久
	for(i=0;i<n;++i)
		if(a[0]==b[i])
		{
			for(j=i;j<n;++j)
				p[j]=1;
			break;
		}
		else p[i]=0;
	for(i=0;i<n;++i)
		if(b[0]==a[i])
		{
			for(j=i;j<n;++j)
				q[j]=1;
			break;
		}
		else q[i]=0;
	for(i=1;i<n;++i)
	{
		z[0]=q[i];
		for(j=1;j<n;++j)
			if(a[i]==b[j])
			{
				z[j]=p[j-1]+1;
			}
			else z[j]=p[j]>z[j-1]?p[j]:z[j-1];
		for(k=0;k<n;++k)
			p[k]=z[k];
	}
	printf("%d\n",n-p[n-1]);
	return 0;
}

• Re:原来自己SB了，改5000为5001就OK了。惨。。。。 (0) tbaitm 2006-09-19 17:05:05