必须要批评下自己了，首先就是这个题目的迟疑不定，去年做字典树的时候就碰到这个题目了，当时没什么好的想法，就暂时搁置了，其实想法应该有很多，只是居然没想到。
同样都是对单词进行建树，并插入可能值，但是拨号键盘上的字母是对应多个的，给定拨号序列，有多种可能情况 输出其中最可能的一种，肯定要想到搜索啊，而且拨号数目不超过100，每个按键最多只对应4个字母，复杂度并不高，所以用dfs是可行的，对于每次递归深度，dfs找到最大的可能值的情况并输出。
接下来就是要批评自己了，下午一点钟开始做这个题目，居然被一个小bug搞了一个多小时，都没过样例，就是我的dfs写挫了，而且我迟迟没找到原因。。。真的要反省自己的代码编写能力了。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int tot; char s[110]; char press[10][5]; char num[110]; int ansd; char anss[110],finds[110]; bool flag; struct node { node* ch[27]; int cur,deep; } tree[200000]; node* newNode() { node* p; p=&tree[tot++]; for (int i=0;i<27;i++) { p->ch[i]=NULL; } p->cur=0; p->deep=0; return p; } void insertn(node* root,char* s1,int fee) { node* p=root; int i=0,k; //puts(s1); while (s1[i]) { k=s1[i]-‘a‘; if (p->ch[k]==NULL) { //cout<<s1[i]<<" "<<p->deep<<endl; p->ch[k]=newNode(); } p->ch[k]->deep=i++; p->ch[k]->cur+=fee; p=p->ch[k]; } } void init() { strcpy(press[2],"abc"); strcpy(press[3],"def"); strcpy(press[4],"ghi"); strcpy(press[5],"jkl"); strcpy(press[6],"mno"); strcpy(press[7],"pqrs"); strcpy(press[8],"tuv"); strcpy(press[9],"wxyz"); } void dfs(node* rt,char* s1,int maxd,int d) { node* p=rt; if (d==maxd) { if (p->cur>ansd){ flag=1; ansd=p->cur; for (int i=0;i<d;i++) anss[i]=finds[i]; anss[d]=‘\0‘; } return; } int k=s1[d]-‘0‘; for (int i=0;press[k][i];i++) { int q=press[k][i]-‘a‘; if (p->ch[q]!=NULL) { finds[d]=press[k][i]; } else continue; dfs(p->ch[q],s1,maxd,d+1); } } void test(node* root) { node* p=root; for (int i=0;i<27;i++) { char c=i+‘a‘; cout<<c<<" "<<i<<endl; if (p->ch[i]!=NULL) puts("Yes"); else puts("NO"); if (p->ch[i]!=NULL){ // cout<<c<<" "<<p->deep<<endl; // p=p->ch[i]; //test(p); } } } int main() { //freopen("d:\\hdu_1298.txt","w",stdout); int t,w,p,m,a,kase=0; scanf("%d",&t); init(); while (t--) { tot=0; node* root=newNode(); root->deep=-100; scanf("%d",&w); for (int i=0;i<w;i++) { scanf("%s %d",s,&p); //puts(s); //cout<<root->deep<<endl; //node*r1=root; //cout<<root->deep<<endl; insertn(root,s,p); //cout<<root->deep<<endl; } //test(root); scanf("%d",&m); printf("Scenario #%d:\n",++kase); for (int i=0;i<m;i++) { scanf("%s",num); //puts(num); ansd=0; flag=false; int len=strlen(num); for (int i=1;i<len;i++) { ansd=0; if (flag||i==1){ flag=false; dfs(root,num,i,0); } if (flag) puts(anss); else puts("MANUALLY"); } printf("\n"); } printf("\n"); } return 0; }
HDU 1298 T9 字典树+DFS,布布扣,bubuko.com
原文：http://www.cnblogs.com/kkrisen/p/3599275.html