• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0

            經(jīng)典的動(dòng)態(tài)規(guī)劃題。

            d[i][j]表示把從1..ij..n變成回文詞最少需要的字符個(gè)數(shù)。

            則:d[i][j]=min(d[i][j],d[i-1][j+1]) s[i]==s[j]

            d[i][j]=min(d[i][j],d[i-1][j]+1)

                d[i][j]=min(d[i][j],d[i][j+1]+1)

            以下是我的程序:

            #include<stdio.h>
            #define maxn 5005
            #define maxint 20000
            #define min(a,b) (a<b?a:b)
            char ch,s[maxn]={0};
            short i,j,n,ans,d[maxn][maxn];
            int main()
            {
                freopen(
            "palin.in","r",stdin);
                freopen(
            "palin.out","w",stdout);
                scanf(
            "%ld\n",&n);
                
            for(i=1;i<=n;i++)
                  scanf(
            "%c",&s[i]);
                
            for(i=0;i<=n+2;i++)
                  
            for(j=0;j<=n+2;j++)
                    d[i][j]
            =maxint;
                
            // Init
                d[0][n+1]=0;
                d[
            0][n]=1;
                d[
            1][n+1]=1;
                
            // 邊界 
                for(i=1;i<=n+1;i++)
                  
            for(j=n+1;j>=i;j--)
                  
            {
                     
            if(s[i]==s[j])
                       d[i][j]
            =min(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);
                  }

                
            // DP
                ans=maxint;
                
            for(i=1;i<=n;i++)
                
            {
                   ans
            =min(ans,d[i][i]);
                   ans
            =min(ans,d[i][i+1]);
                }

                
            // Find Answer
                printf("%d\n",ans);
            return 0;
            }

            posted on 2010-01-06 20:05 lee1r 閱讀(317) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 題目分類:動(dòng)態(tài)規(guī)劃
            久久久噜噜噜www成人网| 欧美久久久久久午夜精品| 无码人妻久久一区二区三区免费| 色综合久久久久综合体桃花网| 久久久无码精品亚洲日韩按摩 | 91精品国产9l久久久久| 欧美伊香蕉久久综合类网站| 久久精品国产亚洲Aⅴ蜜臀色欲| 色天使久久综合网天天| 亚洲国产精品久久66| 18禁黄久久久AAA片| 久久国产热这里只有精品| 久久久无码精品亚洲日韩蜜臀浪潮| 久久中文字幕无码专区| 99久久99久久| 久久久SS麻豆欧美国产日韩| 国产成人精品久久亚洲| 久久久久久午夜成人影院| 久久精品国产亚洲av麻豆图片| 日本免费久久久久久久网站| 浪潮AV色综合久久天堂| 久久精品国产男包| 亚洲欧美日韩精品久久亚洲区 | 国产精品九九久久免费视频| 久久这里只有精品18| 久久中文字幕人妻熟av女| 久久久网中文字幕| 久久精品国产一区二区三区不卡| 久久人人爽人人爽人人片AV不 | 国产A三级久久精品| 香蕉aa三级久久毛片| 久久久久亚洲爆乳少妇无 | 精品乱码久久久久久夜夜嗨| 久久精品国产精品青草| 久久99精品久久久久久| 国产成人久久精品区一区二区| 久久久久免费看成人影片| 97久久超碰国产精品旧版| 国产99久久精品一区二区| 婷婷综合久久狠狠色99h| 岛国搬运www久久|