#include <iostream>
using namespace std;
char str[5000];
short cost[3][5000];
int mincost(int i,int j)
{
	if(i==1||i==0)
		return 0;
	else
	{
		if(str[j]==str[j+i-1])
			return cost[(i+1)%3][j+1];
		else
		{   
			int k1=cost[(i+2)%3][j]+1;
		    int k2=cost[(i+2)%3][j+1]+1;
			return (k1>k2?k2:k1);
		}
		
	}
}
void main()
{

	int N;
	scanf("%d %s",&N,str);
    int i,j;
	for(i=0;i<=N;i++)
	 for(j=0;j<=N-i;j++)
	 {
		 cost[i%3][j]=mincost(i,j);
     }
	printf("%d",cost[N%3][0]);

}

• 考虑一下回文数的特点，dp的时候有点技巧 (0) pladene 2003-12-29 10:18:21
  • Re:考虑一下回文数的特点，dp的时候有点技巧 (62) kkk 2004-12-03 14:12:04
    • bug?只是对于这个题目，g++比较快而已 (118) hawk 2004-12-03 14:26:22
  • Re:考虑一下回文数的特点，dp的时候有点技巧 (13) bbflyer 2005-08-25 11:31:45