infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
简单的DP题!不过做得时候要小心!不然很容易出错.
状态转移方程为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;//结束条件
        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[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){//检查是否匹配,且只有当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 阅读(323) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理