|
Posted on 2009-10-21 20:54 Uriel 阅读(494) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 DP
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; }
|