• <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>

            infinity

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              36 隨筆 :: 0 文章 :: 25 評論 :: 0 Trackbacks
            簡單的DP題!不過做得時候要小心!不然很容易出錯.
            狀態(tài)轉(zhuǎn)移方程為f[i]=max{f[k]+1};{k>=1&&k<=i-1 && f[k]>=0 }

            #include<stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            char num[101],dict[50001][51],len[50001],map[256];
            int f[101],c[101][2],minlen,i,j,k,n;
            void init(){
                map[
            'i']=map['j']='1';
                map[
            'a']=map['b']=map['c']='2';
                map[
            'd']=map['e']=map['f']='3';
                map[
            'g']=map['h']='4';
                map[
            'k']=map['l']='5';
                map[
            'm']=map['n']='6';
                map[
            'p']=map['r']=map['s']='7';
                map[
            't']=map['u']=map['v']='8';
                map[
            'w']=map['x']=map['y']='9';
                map[
            'o']=map['q']=map['z']='0';
            }
            void output(int t){
                
            if(t<1return ;
                output(c[t][
            0]);
                printf(
            "%s ",dict[c[t][1]]);
            }
            int main(){
                init();
                
            while(1){
                    num[
            0]='0';// 賦初值,否則strlen(num)返回值一直為1
                    scanf("%s",num+1);
                    
            if(strcmp(num+1,"-1")==0break;//結(jié)束條件
                    scanf("%d",&n);
                    minlen
            =101;

                    
            for(i=1;i<=n;i++) {
                        scanf(
            "%s",dict[i]);
                        len[i]
            =strlen(dict[i]);
                        
            if(len[i]<minlen) minlen=len[i];
                    }

                    
            int tmp=strlen(num)-1;
                    
            if(minlen>tmp){printf("No solution.\n");continue;}//剪枝

                    memset(f,
            -1,sizeof(f));//負(fù)值代表不能由單詞串成

                    f[0]=0;

                    
            int ind;
                    
            for(i=minlen;i<=strlen(num)-1;i++){//DP
                        int min=1000;
                        
            for(j=1;j<=n;j++){//枚舉所有的單詞
                            if(len[j]<=&& map[dict[j][len[j]-1]]==num[i] && f[i-len[j]]>=0){//檢查是否匹配,且只有當(dāng)f[i-len[j]]>=0
                                int flag=0;                                                   //f[i]才可能>=0,否則,f[i]無法由單詞串成
                                for(k=i;k>=i-len[j]+1;k--){
                                    
            if(num[k]!=map[dict[j][len[j]-i+k-1]]) {flag=1;break;}
                                }
                                
            if(flag==0 && f[i-len[j]]+1<min) {min=f[i-len[j]]+1;ind=j;}//
                            }
                        }
                        f[i]
            =min;
                        
            if(f[i]==1000) f[i]=-1;
                        
            else {c[i][0]=i-len[ind];c[i][1]=ind;}
                    }
                    
                    
            if(f[strlen(num)-1]==-1) printf("No solution.\n");
                    
            else {
                        output(strlen(num)
            -1);
                        printf(
            "\n");
                    }
                }
            }




            posted on 2008-11-02 13:09 infinity 閱讀(338) 評論(0)  編輯 收藏 引用 所屬分類: acm
            97精品伊人久久大香线蕉| 国产日韩久久免费影院| 久久免费看黄a级毛片| 超级97碰碰碰碰久久久久最新| 久久久久久伊人高潮影院| 少妇人妻88久久中文字幕| 久久亚洲综合色一区二区三区| 精品久久久久久无码中文字幕| 久久久久久久女国产乱让韩| 狠狠色丁香婷婷久久综合不卡| 亚洲伊人久久综合中文成人网| 国产精品99久久99久久久| 久久久久无码精品国产app| 亚洲中文字幕无码久久精品1| 亚洲国产精品久久久久婷婷软件| 成人综合久久精品色婷婷| 99久久国产主播综合精品| 欧美丰满熟妇BBB久久久| 久久精品免费网站网| 国内精品久久国产大陆| 麻豆av久久av盛宴av| 久久久久久久国产免费看| 99久久99这里只有免费的精品| 亚洲国产成人乱码精品女人久久久不卡 | 久久久亚洲裙底偷窥综合| 久久国产高清字幕中文| 综合久久国产九一剧情麻豆| 久久久WWW成人| 韩国三级中文字幕hd久久精品 | 亚洲AV成人无码久久精品老人| 久久国产成人| 国产精品熟女福利久久AV| 97久久精品国产精品青草| 久久亚洲精品中文字幕| 久久综合国产乱子伦精品免费| 成人综合久久精品色婷婷| 久久精品日日躁夜夜躁欧美| 久久妇女高潮几次MBA| 国产亚洲美女精品久久久2020| 青青草原综合久久大伊人| 免费久久人人爽人人爽av|