https://vjudge.net/problem/UVA-10453
给出一个字符串，问最少添加几个字符使其变为回文串，并输出任意一种答案。就是一个类似于LCS的题目，而且简化了一下，只会出现三种情况。令f[i][j]表示这个字符串i~j位的答案，当si==sj f[i][j]=f[i+1][j-1] ; 否则f[i][j]=MIN{f[i+1][j],f[i][j-1]}+1, 取一个最小值就是答案，最后递归输出一下。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
char s[];
int f[][],N;
void out(int l,int r)
{
if(r<l) return;
if(l==r){printf("%c",s[l]);return ;}
if(s[l]==s[r]&&f[l][r]==f[l+][r-]){
printf("%c",s[l]);
out(l+,r-);
printf("%c",s[l]);
}
else{
if(f[l][r]==f[l][r-]+){
printf("%c",s[r]);
out(l,r-);
printf("%c",s[r]);
}
else{
printf("%c",s[l]);
out(l+,r);
printf("%c",s[l]);
}
}
}
int main()
{
int N,M,i,j,k;
while(gets(s+)){
int n=strlen(s+);N=n;
//if(!n){puts("0");continue;}
memset(f,,sizeof(f));
for(int len=;len<=n;++len)
{
for(i=,j=len;j<=n;++i,++j)
{
f[i][j]=inf;
if(s[i]==s[j]) f[i][j]=min(f[i][j],f[i+][j-]);
f[i][j]=min(f[i][j],+min(f[i+][j],f[i][j-]));
}
}
cout<<f[][n]<<' ';
out(,n);
puts("");
}
return ;
}