题目大意：

插入最少的字符，使原字符串成为回文串。

题解:

　　LCS问题，将字符串反转，然后求这俩字符串的LCS，总长度减去LCS即可（多组输入）。

　　N最大是5E3，直接用二维数组会超内存。所以要用到滚动数组。

　　code:

#include
using namespace std;
const int N=5E3+;
int dp[][N];
char s1[N],s2[N];
int main(){
int n;
ios::sync_with_stdio();
while(cin>>n){
memset(dp,,sizeof dp);
cin>>s1+;
for(int i=;i<=n;i++) s2[i]=s1[i];
reverse(s1+,s1++n);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(s1[i]==s2[j]) dp[i%][j]=max(dp[i%][j],dp[(i-)%][j-]+);
else dp[i%][j]=max(dp[(i-)%][j],dp[i%][j-]);
}
cout<<n-dp[n%][n]<<endl;
}

return ;  

}