回文字符串
时间限制： ms &|& 内存限制：65535 KB
描述所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如"aba"。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。
输入第一行给出整数N（0&N&100）接下来的N行，每行一个字符串，每个字符串长度不超过1000.输出每行输出所需添加的最少字符数样例输入
分析：d[i][j]表示从第 i 到第 j 的最优解；if(a[i]==a[j]) d[i][j]=d[i+1][j-1];d[i][j]=max{d[i][j] , d[i+1][j]+1 , d[i][j-1]+1};
1 #include&iostream&
2 #include&cstdio&
3 #include&cstring&
4 #define N 1010
5 using namespace
7 int d[N][N];
8 char a[N];
10 int min(int x,int y)
return x&y?x:y;
15 int main()
int i,j,p,n,
scanf("%d",&test);
while(test--)
scanf("%s",a+1);
n=strlen(a+1);
for(i=1;i&=n;i++) d[i][i]=d[i][i-1]=0;
for(p=1;p&n;p++)
for(i=1;i&=n-p;i++)
d[i][j]=10000;
if(a[i]==a[j]) d[i][j]=d[i+1][j-1];
d[i][j]=min(d[i][j],d[i+1][j]+1);
d[i][j]=min(d[i][j],d[i][j-1]+1);
printf("%d\n",d[1][n]);
阅读(...) 评论()}