GDUT 校赛02 dp回文串

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 using namespace std;
 8 const int maxn=5001;
 9 int n,m,t;
10 short dp[maxn][maxn];
11 char s[maxn];
12 int main()
13 {
14     int i,j,k;
15     #ifndef ONLINE_JUDGE
16     freopen("1.in","r",stdin);
17     #endif
18     scanf("%d",&t);
19     while(t--)
20     {
21         int len=0;
22         scanf("%d",&len);
23         scanf("%s",s);
24         for(i=0;i<len;i++)  dp[i][i]=1;
25         for(k=1;k<len;k++)
26         {
27             for(i=0;i+k<=len;i++)
28             {
29                 int j=k+i;
30                 if(s[i]!=s[j])  dp[i][j]=dp[i+1][j-1];
31                 else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
32             }
33         }
34         printf("%d\n",dp[0][len-1]);
35     }
36     return 0;
37 }