poj1159

 1 /*/所要插入的个数是n-输入的序列和他逆序列的最长公共子串长度**/
 2 
 3 #include<string.h>
 4 #include<stdio.h>
 5 char a[5010],b[5010];
 6 short int dp[5010][5010];//用int会爆内存
 7 int LCS(int n,int m)
 8 {
 9     int i,j;
10     for(i=1;i<=n;i++)
11         for(j=1;j<=m;j++)
12         {
13             if(a[i-1]==b[j-1])
14             {
15                 dp[i][j]=dp[i-1][j-1]+1;
16                 //dir[i][j]=1;
17             }
18             else if(dp[i-1][j]>=dp[i][j-1])
19             {
20                 dp[i][j]=dp[i-1][j];
21             //    dir[i][j]=0;
22             }
23             else
24             {
25                 dp[i][j]=dp[i][j-1];
26                 //dir[i][j]=2;
27             }
28         }
29         return dp[n][m];
30 }
31 int main()
32 {
33    int i,j,n;
34    while(scanf("%d",&n)!=EOF)
35    {
36        getchar();
37        gets(a);
38        
39        for(i=n-1,j=0;i>=0;i--,j++)
40        {
41            b[j]=a[i];
42        }
43        //printf("%s
%s
",a,b);
44        printf("%d
",n-LCS(n,n));
45    }
46    return 0;
47 }