1 //#define LOCAL 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstring> 6 using namespace std; 7  8 const int maxn = 5000 + 5; 9 char s1[maxn], s2[maxn];10 int dp[2][maxn];11 12 void Reverse(char str[], int len)13 {14     int i, t;15     for(i = 0; i < len/2; ++i)16     {17         t = str[i];18         str[i] = str[len - 1 - i];19         str[len - 1 - i] = t;20     }21 }22 23 int main(void)24 {25     #ifdef LOCAL26         freopen("1513in.txt", "r", stdin);27     #endif28     int len;29     while(scanf("%d", &len) == 1)30     {31         scanf("%s", s1);32         memcpy(s2, s1, sizeof(s1));33         Reverse(s2, len);34         int i, j;35         memset(dp, 0, sizeof(dp));36         int cur = 1,ans;37         for(i = 1; i <= len; ++i)38         {39             for(j = 1; j <= len; ++j)40             {41                 if(s1[i-1] == s2[j-1])42                     dp[cur][j] = dp[1-cur][j-1] + 1;43                 else44                     dp[cur][j] = max(dp[1-cur][j], dp[cur][j-1]);45             }46             cur = 1 - cur;47         }48         ans = len - dp[len&1][len];49         printf("%d\n", ans);50     }51     return 0;52 }