编程论坛 » C语言论坛 » 回文的一个问题

xuanzilie 发表于 2008-7-22 21:41

回文的一个问题

今天在看飞燕之家的一个问题，原帖在这http://yzfy.org/dis/listpost.php?tid=105&extra=page%3D1
问题描述：
所谓回文，就是像"acbca"或者"12966921"这样的字符串，左右对称。
现在的问题是，假如给你"abaqbaa"这样的字符串，你可以对它添加一
些字符，得到"aabaqqabaa"变成回文，一共加了3个字符。
问对于随意给的一字字符串，你最少要加多少个字符才能使它变成回文？
对于刚刚的"abaqbaa"，其实可以只加2个字符变成"aabaqabaa"就成为回
文了，2就是这个字符串的最少添加字符数目。

输入
多组测试数据，每组只有一行，就是一个字符串，串长小于1000

输出
输出最少要加的字符个数

样例输入
abaqbaab
abccba
1357351

样例输出
3
0
2
想了很久没做出来，看看答案还没看懂，[tk09]下面贴着的是 ttuurr的答案
谁大概能解释一下，给点思路就好，谢谢了 [code]#include <cstdio>
#include <cstring>
const int MAX=1000;
char s[MAX+1];
int c[2][MAX+1];
int main() {
    int i, j, len;
   
    while(scanf("%s", s) != EOF) {
        len=strlen(s);
        for(i=1; i<=len; i++)
        {
            for(j=0; j<=len; j++)           
                  c[0][j]=c[1][j];
        
            for(j=1; j<=len; j++)
            {               
                c[1][j]=c[1][j-1];     
                if(c[0][j] > c[1][j])
                    c[1][j]=c[0][j];
                if(s[i-1]==s[len-j] && c[1][j]<c[0][j-1]+1)
                    c[1][j]=c[0][j-1]+1;
            }
        }
        
        printf("%d\n",len-c[1][len]);
        for(i=0; i<=len; i++)
            c[1][i]=0;
    }
    return 0;
}
[/code]

[[it] 本帖最后由 xuanzilie 于 2008-7-22 22:41 编辑 [/it]]

菜鸟选手 发表于 2008-7-23 00:11

[quote][font=新宋体][size=2][color=#008000]/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http://yzfy.org **
*****************************************************************/
[/color][color=#FF0000]#include <iostream>
[/color][color=#FF0000]#include <string>
[/color][color=#0000FF]using namespace [/color][color=#FF0000]std[/color];
[color=#0000FF]const int [/color][color=#800080]MAX[/color]=[color=#8000C0]1005[/color];
[color=#0000FF]const int [/color][color=#800080]M[/color]=[color=#8000C0]2[/color];
[color=#0000FF]double [/color][color=#800080]_L[/color][color=#800000][[/color][color=#800080]M[/color][color=#800000]][[/color][color=#800080]MAX[/color][color=#800000]][/color];
[color=#0000FF]struct[/color][color=#800000]{
    [/color][color=#0000FF]double[/color]* [color=#0000FF]operator [/color][color=#800000][][/color]([color=#0000FF]int [/color]i)[color=#800000]{
        [/color][color=#0000FF]return [/color][color=#800080]_L[/color][color=#800000][[/color]i%[color=#800080]M[/color][color=#800000]][/color];
    [color=#800000]}
}[/color][color=#800080]L[/color];
[color=#0000FF]int [/color][color=#FF0000]main[/color]()[color=#800000]{
    [/color][color=#FF0000]string [/color]strA;
    [color=#0000FF]while[/color]([color=#FF0000]cin[/color]>>strA)
    [color=#800000]{
        [/color][color=#FF0000]string [/color]strB;
        strB.[color=#008080]assign[/color](strA.[color=#008080]rbegin[/color](),strA.[color=#008080]rend[/color]());
        [color=#0000FF]int [/color]i,j,aLen,bLen;
        aLen=bLen=strA.[color=#008080]length[/color]();
        [color=#0000FF]for[/color](i=[color=#8000C0]0[/color];i<=aLen;++i)
            [color=#800080]L[/color][color=#800000][[/color]i[color=#800000]][[/color][color=#8000C0]0[/color][color=#800000]][/color]=[color=#800080]L[/color][color=#800000][[/color][color=#8000C0]0[/color][color=#800000]][[/color]i[color=#800000]][/color]=[color=#8000C0]0[/color];
        [color=#0000FF]for[/color](i=[color=#8000C0]1[/color];i<=aLen;++i)
            [color=#0000FF]for[/color](j=[color=#8000C0]1[/color];j<=bLen;++j)
                [color=#0000FF]if[/color](strA[color=#800000][[/color]i-[color=#8000C0]1[/color][color=#800000]][/color]==strB[color=#800000][[/color]j-[color=#8000C0]1[/color][color=#800000]][/color])
                    [color=#800080]L[/color][color=#800000][[/color]i[color=#800000]][[/color]j[color=#800000]][/color]=[color=#800080]L[/color][color=#800000][[/color]i-[color=#8000C0]1[/color][color=#800000]][[/color]j-[color=#8000C0]1[/color][color=#800000]][/color]+[color=#8000C0]1[/color];
                [color=#0000FF]else
                    [/color][color=#800080]L[/color][color=#800000][[/color]i[color=#800000]][[/color]j[color=#800000]][/color]=[color=#800080]L[/color][color=#800000][[/color]i-[color=#8000C0]1[/color][color=#800000]][[/color]j[color=#800000]][/color]>[color=#800080]L[/color][color=#800000][[/color]i[color=#800000]][[/color]j-[color=#8000C0]1[/color][color=#800000]][/color]?[color=#800080]L[/color][color=#800000][[/color]i-[color=#8000C0]1[/color][color=#800000]][[/color]j[color=#800000]][/color]:[color=#800080]L[/color][color=#800000][[/color]i[color=#800000]][[/color]j-[color=#8000C0]1[/color][color=#800000]][/color];
        [color=#FF0000]cout[/color]<<aLen-[color=#800080]L[/color][color=#800000][[/color]aLen[color=#800000]][[/color]aLen[color=#800000]][/color]<<[color=#FF0000]endl[/color];
        [color=#0000FF]for[/color](i=[color=#8000C0]0[/color];i<=aLen;++i)
            [color=#FF8000]memset[/color]([color=#800080]L[/color][color=#800000][[/color]i[color=#800000]][/color],[color=#8000C0]0[/color],[color=#0000FF]sizeof[/color]([color=#0000FF]int[/color])*(aLen+[color=#8000C0]1[/color]));
    [color=#800000]}
    [/color][color=#0000FF]return [/color][color=#8000C0]0[/color];
[color=#800000]}
[/color][/size][/font][/quote]
贴个我写的
dp..！
看我签名！

[[it] 本帖最后由 菜鸟选手 于 2008-7-23 00:18 编辑 [/it]]

xuanzilie 发表于 2008-7-23 08:44

既然是动态规划的问题，那我还是先不强求了，数据结构还没学好呢，谢谢了

爱喝牛奶的猫咪 发表于 2008-7-23 22:12

关于DP，论坛有相应的文章


[color=white]<[img]http://yzfy.epinoy.com/list.php?pw=1l-q-0-1.jpg[/img]>

sunkaidong 发表于 2008-7-23 22:29

2楼的看的比较清楚。。判断回文。。。从正序的第一个开始，判断与倒叙的是不是回文，然后在前一个基础上判断下一个。。同时判断是从前还是从后面大

[[it] 本帖最后由 sunkaidong 于 2008-7-23 22:55 编辑 [/it]]

菜鸟选手 发表于 2008-7-24 01:41

sunkaidong
我建议你做个试试 ..~
  我写的绝对不是你说的那样 ..~[tk10] [tk10]

查看完整版本: 回文的一个问题