HDU 1298 T9(手机输入法相关，字典树+dfs)(二)

Terminate the output for every number sequence with a blank line, and print an additional blank line at the end of every scenario.

Sample Input
2
5
hell 3
hello 4
idea 8
next 8
super 3
2
435561
43321
7
another 5
contest 6
follow 3
give 13
integer 6
new 14
program 4
5
77647261
6391
4681
26684371
77771

Sample Output
Scenario #1:
i
id
hel
hell
hello

i
id
ide
idea

Scenario #2:
p
pr
pro
prog
progr
progra
program

n
ne
new

g
in
int

c
co
con
cont
anoth
anothe
another

p
pr
MANUALLY
MANUALLY

题目大意：
在以前，手机输入法很麻烦，因为只有9个键，而字母有26个，所以一个键上同时包含这几个字母，这样的话，为了打出一个字母可能要按几次。比如键5有“JKL”， 如果要输入K，那么就要连按两次。
这样的输入法很麻烦。所以一家公司发明了T9技术输入法。这种输入法内置这很多英语单词，它可以根据英语出现的频率，是否存在等信息，每个字母只要按一次，就可以有想要的预选单词。
例如，假设输入法只内置了一个单词“hell”， 那么只需要按4355便可以出来。
注意，如果有一个单词hell， 那么这个单词的所有前缀，h, he, hel, 也当作是存在的。

分析与总结：
这题貌似和实际应用关系还是挺大。
按照要求建好字典树，插入一个单词时，一路下去都要加上频率p.
然后就是要用dfs，求出频率最大的那个单词输出。

做这题时，没想到竟然1A了，笑死

代码：
[cpp]
#include
#include
#include
#include
using namespace std;

const int KIND = 26;
const int MAXN = 15000;
int cnt_node;

vectorg[10];
char input[105];
char ans[105];
int num, Max;
bool flag;

struct node{
int prefix;
node *next[KIND];
void init(){
prefix=0;
memset(next, 0, sizeof(next));
}
}Heap[MAXN];

inline node* newNode(){
Heap[cnt_node].init();
return &Heap[cnt_node++];
}
void insert(node *root, char *str, int n){
for(char *p=str; *p; ++p){
int ch=*p-'a';
if(root->next[ch]==NULL)
root->next[ch] = newNode();
root = root->next[ch];
root->prefix += n;
}
}
void dfs(node *root, char *str, int pos){ //str保存输出结果
if(root==NULL)return;
if(pos >= num){
if(root->prefix > Max){
strcpy(ans, str);
Max=root->prefix;
}
flag=true;
return ;
}
int u=input[pos]-'0';
for(int i=0; i str[pos] = g[u][i]+'a';
dfs(root->next[g[u][i]], str, pos+1);
str[pos] = 0;
}
}

int main(){
int T,n,p,cas=1;
char str[105];

// 键盘设置, 貌似这样写复杂了...
for(int i=0; i<10; ++i) g[i].clear();
g[2].push_back(0), g[2].push_back(1), g[2].push_back(2);
g[3].push_back(3), g[3].push_back(4), g[3].push_back(5);
g[4].push_back(6), g[4].push_back(7), g[4].push_back(8);
g[5].push_back(9), g[5].push_back(10), g[5].push_back(11);
g[6].push_back(12), g[6].push_back(13), g[6].push_back(14);
g[7].push_back(15), g[7].push_back(16), g[7].push_back(17),g[7].push_back(18);
g[8].push_back(19), g[8].push_back(20), g[8].push_back(21);
g[9].push_back(22), g[9].push_back(23), g[9].push_back(24), g[9].push_back(25);

scanf("%d",&T);
while(T--){
scanf("%d",&n);
printf("Scenario #%d:\n", cas++);

// Trie init
cnt_node=0;
node *root = newNode();

for(int i=0; i scanf("%s %d",str,&p);
insert(root, str, p);
}

scanf("%d",&n);
for(int i=0; i scanf("%s", input);
for(int j=0; j memset(str, 0, sizeof(str));
Max=-1;
num=j+1;
flag=false;
dfs(root, str, 0);
if(flag) puts(ans);
else puts("MANUALLY");
}
puts("");
}
puts("");
}