4843042_mle.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 31 行

#include<iostream>
using namespace std;
int n;
char x[5010];
char y[5010];
int num[5010][5010];
void testout()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++) cout<<num[i][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])num[i][j]=num[i-1][j-1]+1;
			else num[i][j]=num[i-1][j]>num[i][j-1]?num[i-1][j]:num[i][j-1];
		}
	}
	//testout();
	cout<<n-num[n-1][n-1]<<endl;
	return 0;
}