題意：
? ? ? 給你一些按鍵順序，讓你輸出每一步中概率最大的那個單詞，這里的概率計(jì)算方
法好好看看別弄錯了，一開始就是因?yàn)榕e了，各種wa，比如 abc 1 ,ab 1，那么
ab 的概率就是2 ，而不是4，一開始我誤認(rèn)為是所有單詞累加后再把每個單詞的每個字母累加作為當(dāng)前單詞的概率的，結(jié)果各種wa。

思路：
? ? ? 先建一顆字典樹，為了是節(jié)省內(nèi)存，方便更新，和快速查詢，其實(shí)hash也可以

，不過我自己一般都是用map去hasn，目測這個題目map去hash會TLE，因?yàn)橐O(shè)計(jì)到拆串和各種mark，map是排序的，說遠(yuǎn)了，建樹的時候記得更新概率值，然后就是暴力深搜，把每一個長度的都找出來，然后開個數(shù)組更新當(dāng)前的最有和記錄答案串，深搜的時候a,b,c...這樣自然就是字典序.

#include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct Tree {Tree *next[26];int v; }Tree;Tree root; char now[111] ,ans_str[222][111]; int max[111] ,Key[111]; int jianzi[8] = {3 ,3 ,3 ,3 ,3 ,4 ,3 ,4};char mk[8][4] = {'a' ,'b' ,'c' ,'0' ,'d' ,'e' ,'f' ,'0','g' ,'h' ,'i' ,'0' ,'j' ,'k' ,'l' ,'0','m' ,'n' ,'o' ,'0' ,'p' ,'q' ,'r' ,'s','t' ,'u' ,'v' ,'0' ,'w' ,'x' ,'y' ,'z'};void Buid_Tree(char *str ,int vv) {int len = strlen(str);Tree *p = &root ,*q;for(int i = 0 ;i < len ;i ++){int id = str[i] - 'a';if(p -> next[id] == NULL){q = (Tree *) malloc(sizeof(root));q -> v = vv;for(int j = 0 ;j < 26 ;j ++)q -> next[j] = NULL;p -> next[id] = q;p = p -> next[id];}else{p = p -> next[id];p -> v += vv;}} }int Find(char *str) {int len = strlen(str);Tree *p = &root;int sum = 0;for(int i = 0 ;i < len ;i ++){int id = str[i] - 'a';p = p -> next[id];if(p == NULL) return -1;sum += p -> v;}return p -> v; }void DFS(int ii ,int n) {if(ii == n + 1) return;for(int i = 0 ;i < jianzi[Key[ii] - 2] ;i ++){now[ii-1] = mk[Key[ii] -2][i];now[ii] = '\0';int sum = Find(now);if(sum == -1) continue;if(sum > max[ii]){max[ii] = sum;for(int j = 0 ;j <= ii ;j ++)ans_str[ii][j] = now[j];}DFS(ii + 1 ,n);} }int main () {int t ,n ,m ,i ,vv ,cas = 1;char str[111];scanf("%d" ,&t);while(t--){for(i = 0 ;i < 26 ;i ++)root.next[i] = NULL;scanf("%d" ,&n);while(n--){scanf("%s %d" ,str ,&vv);Buid_Tree(str ,vv);}scanf("%d" ,&m);printf("Scenario #%d:\n" ,cas ++);while(m--){memset(max ,255 ,sizeof(max));scanf("%s" ,str);int len = strlen(str);int last = str[len-1] - '0';for(i = 0 ,len --;i < len ;i ++)Key[i+1] = str[i] - '0';DFS(1 ,len);for(i = 1 ;i <= len ;i ++)if(max[i] == -1) puts("MANUALLY");else puts(ans_str[i]);puts("");}puts("");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 1298 字典树 + DFS (模拟T9文本输入)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。