本文主要是介绍URAL 1002. Phone Numbers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意就是，已知一串数字，按照题目给的对应表，转换成字母之后，能否由给定的单词组成。要求
输出单词数最小的任意一组答案，或输出无解。
用的DP。
dp[ i ]表示以前i个字母可以组成的最少单词数量。
最后dp [ 总字符数量 ] 就是最少单词个数。
再根据path[ i ] 记录的路径，返回去输出每个单词。
具体见代码:
#define K2(a,b,t) case a:case b:temp=t;break;
#define K3(a,b,c,num) case a:case b:case c:temp=num;break;using namespace std;char a[101];
struct W{char w[50];//存单词 char num[50];//存单词转化成数字后的版本 int n;//字符个数 bool operator <(const W &B)const{return n>B.n;}
}word[50000];
int N;//单词个数
int ALL;//电话的号码个数
void trans();//将单词转换成数字
void show(char *a);//显示字符串 int dp[101];//表示以前i个字母可以组成的最少单词数量。
int path[101];//path[i]表示，前i个字母中，最后一个单词的开头。
int wo[101];//word[i]表示，前i个字母中，最后一个单词的编号
void F(int i);//输出单词
int main(void)
{while(scanf("%s",a)==1){a[101]='\0';if(a[0]=='-') break;ALL=0;while(a[ALL]) ALL++;cin>>N;//输入单词 for(int i=0;i<N;i++){scanf("%s",word[i].w);}//翻译 trans();sort(word,word+N);//计算memset(dp,-1,sizeof(dp));dp[0]=0;for(int i=0;i<ALL;i++){//对每个位置 if(~dp[i]) //如果可以达到这一点 for(int j=0;j<N;j++){//则搜每个单词 if(i+word[j].n<=ALL){//如果长度合适 //判断是否可以放置这个词char temp[50];strncpy(temp,&a[i],word[j].n);temp[word[j].n]='\0';if(!strcmp(temp,word[j].num)) {//如果可以 if(~dp[i+word[j].n]) {//若已经有结尾位置一样的字串 if(dp[i]+1<dp[i+word[j].n]){//若字数少于它则更新 dp[i+word[j].n]=dp[i]+1,path[i+word[j].n]=i,wo[i+word[j].n]=j;}}else{//若没有，直接更新 dp[i+word[j].n]=dp[i]+1,path[i+word[j].n]=i,wo[i+word[j].n]=j;}} }} } //输出if(~dp[ALL]) F(ALL);else printf("No solution.\n"); }
return 0;
}
void F(int i){//输出单词if(path[i]) F(path[i]);show(word[wo[i]].w);if(i==ALL) printf("\n");else printf(" ");
}
void show(char *a){//显示字符串while(*a){printf("%c",*a++);}
}
void trans(){//将单词转换成数字 for(int i=0;i<N;i++){int t=0;while(word[i].w[t]){char &temp=word[i].num[t];switch(word[i].w[t]){K2('i','j','1');K3('a','b','c','2');K3('d','e','f','3');K2('g','h','4');K2('k','l','5');K2('m','n','6');K3('p','r','s','7');K3('t','u','v','8');K3('w','x','y','9');K3('o','q','z','0');}t++;}word[i].n=t;word[i].num[word[i].n]='\0';}
}
这篇关于URAL 1002. Phone Numbers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
