Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1732 Phone numbers---DP

Posted on 2009-10-21 20:54 Uriel 阅读(495) 评论(0)  编辑 收藏 引用 所属分类: POJDP
Regional现场赛前一天晚上纠结很久很久啊。。纪念下。。。
最后C++还是没过,G++AC。。原因不明。。。
/*Problem: 1732  User: Uriel 
   Memory: 5812K  Time: 63MS 
   Language: G++  Result: Accepted
*/


#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>

char sd[27]={'2','2','2','3','3','3','4','4','1','1','5','5','6','6','0','7','0','7','7','8','8','8','9','9','9','0'};
char str[200],s[50010][105],temp[50010][105],num[50010][105];
int dp[200],i,j,leng[50010],len;
int word[200];
int pre[200];
int min(int a,int b)
{
    
return a < b? a:b;
}


void output(int i){
    
if(pre[i]>=0)
    
{
        output(pre[i]);
        
if(pre[i])printf(" ");
    }

    printf(
"%s",s[word[i]]);
}



int main()
{
    
int i,j,n;
    scanf(
"%s",&str[1]);
    scanf(
"%d",&n);
    memset(pre,
-1,sizeof(pre));
    memset(word,
-1,sizeof(word));
    
for(i=0;i<n;i++)
    
{
        scanf(
"%s",s[i]);
        leng[i]
=strlen(s[i]);
        
for(j=0;j<leng[i];j++)
        
{
            num[i][j]
=sd[s[i][j]-'a'];
        }

    }

    len
=strlen(&str[1]);
    memset(dp,
-1,sizeof(dp));
    dp[
0]=0;
    
for(i=1;i<=len;i++)
    
{
        
for(j=0;j<n;j++)
        
{
            
if(i>=leng[j] && strncmp(&str[i-leng[j]+1],num[j],leng[j])==0)
            
{
                
if(dp[i-leng[j]]==-1)continue;
                
int x;
                
if(dp[i]==-1)
                
{
                    x
=dp[i-leng[j]]+1;
                }

                
else
                
{   
                    x
=min(dp[i],dp[i-leng[j]]+1);
                }

                
if(dp[i]!=x)
                
{
                    dp[i]
=dp[i-leng[j]]+1;
                    word[i]
=j;
                    pre[i]
=i-leng[j];
                }

            }

        }

    }

    
if(dp[len]<0)
    
{
        printf(
"No solution.\n");
    }

    
else
    
{
        output(len);
        printf(
"\n");
    }

    
return 0;
}


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