4843078_ac_829ms_328k.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
int n;
char x[5010];
char y[5010];
int prev[5010];
int next[5010];
void testout()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++) cout<<endl;
	}
}
int main()
{
	cin>>n;
	int i,j;
	for(i=1;i<=n;i++){cin>>x[i];y[n+1-i]=x[i];}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(x[i]==y[j]) next[j]=prev[j-1]+1;
			else next[j]=next[j-1]>prev[j]?next[j-1]:prev[j];
			//cout<<next[j]<<" ";
		}
		//cout<<endl;
		for(j=1;j<=n;j++)
		{
			prev[j]=next[j];
		}
	}
	cout<<n-next[n]<<endl;
	return 0;
}