题意: 给一个字符串 ，判断最少插入多少个字符 使字符串成为回文串， 并输出回文串。
思路：先用dp判断需要个数， 再递归输出路径。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define min(a, b)((a)>(b)?(b):(a))
using namespace std; const int maxn = ;
char s[maxn];
int d[maxn][maxn], len; void show(int a, int b)
{
if(a==b)
{
cout<<s[a];
return;
}
if(a>b)
return;
if(s[a] == s[b])
{
cout<<s[a];
show(a+, b-);
cout<<s[b];
}
else
{
if(d[a+][b] < d[a][b-])
{
cout<<s[a];
show(a+, b);
cout<<s[a];
}
else
{
cout<<s[b];
show(a, b-);
cout<<s[b];
}
}
}
int main()
{
int i, k;
while(cin>>s)
{
len = strlen(s);
memset(d, , sizeof(d));
for(i = ; i < len-; i++)
if(s[i]!=s[i+])
d[i][i+] = ;
for(k = ; k <= len-; k++)
for(i = ; i <len; i++)
{
if(i+k<len)
{
if(s[i] == s[i+k])
d[i][i+k] = d[i+][i+k-];
else
d[i][i+k] = min(d[i+][i+k], d[i][i+k-]) + ;
}
}
cout<<d[][len-]<<" ";
show(, len-);
cout<<endl;
}
return ;
}