HDU 1298 T9（字典树+dfs）

http://acm.hdu.edu.cn/showproblem.php?pid=1298

题意：
模拟手机9键，给出每个单词的使用频率。现在给出按键的顺序，问每次按键后首字是什么（也就是要概率最大的）。

思路：

先建立字典树算出每个前缀出现的概率，然后dfs每种情况，选择概率大的。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn = 1000*1000+5;
 6 
 7 char s[105],ans[105],tmp[105];
 8 
 9 int n, num = 0, p;
10 int pheno[8][4] = {{0,1,2},{3,4,5},{6,7,8},{9,10,11},{12,13,14},{15,16,17,18},{19,20,21},{22,23,24,25}};
11 int key[8] = {3,3,3,3,3,4,3,4};
12 
13 struct Trie
14 {
15     int son[26];
16     int cnt;
17 }t[maxn];
18 
19 void init(int x)
20 {
21     t[x].cnt = 0;
22     memset(t[x].son,0,sizeof(t[x].son));
23 }
24 
25 void insert(char* s, int d)
26 {
27     int u = 0, n = strlen(s);
28     for(int i=0;i<n;i++)
29     {
30         int c = s[i]-'a';
31         if(!t[u].son[c])
32         {
33             num++;
34             init(num);
35             t[u].son[c] = num;
36         }
37         u = t[u].son[c];
38         t[u].cnt += d;
39     }
40 }
41 
42 void dfs(int cur, int u, int len, char* s)
43 {
44      if(cur == len)
45      {
46          if(t[u].cnt > p)
47          {
48              p = t[u].cnt;
49              for(int i=0;i<len;i++)  ans[i] = tmp[i];
50              ans[len] = '';
51          }
52          return;
53      }
54      int k = s[cur]-'2';
55      for(int i=0;i<key[k];i++)
56      {
57          int c = pheno[k][i];
58          if(!t[u].son[c])  continue;
59          tmp[cur] = 'a'+ c;
60          dfs(cur+1, t[u].son[c], len, s);
61      }
62 }
63 
64 int main()
65 {
66     //freopen("in.txt","r",stdin);
67     int T;
68     scanf("%d",&T);
69     int kase = 0;
70     while(T--)
71     {
72         init(0);
73         scanf("%d",&n);
74         for(int i =0;i<n;i++)
75         {
76             scanf("%s%d",s,&p);
77             insert(s,p);
78         }
79         printf("Scenario #%d:
",++kase);
80         int q; scanf("%d",&q);
81         while(q--)
82         {
83             scanf("%s",&s);
84             int len = strlen(s);
85             for(int i=0;i<len-1;i++)
86             {
87                 p = 0;
88                 dfs(0,0,i+1,s);
89                 if(p)  printf("%s
",ans);
90                 else puts("MANUALLY");
91             }
92             if(q)  puts("");
93         }
94         printf("

");
95     }
96     return 0;
97 }