題意：
? ? ? ?給你一些名字，讓你用一臺打印機(jī)去打印這些名字，打印機(jī)只有三個操作
（1）打印的都是小寫字母
（2）每次可以在當(dāng)前字母的后面加一位，或刪除一位。
（3）打印當(dāng)前串
問你最少多少步可以吧所有的名字都打完。

思路：
? ? ? 這個題目首先要看懂題目，不然測試數(shù)據(jù)都模擬不過去，曾加一個字母，刪除一個字母，打印，每一種都算是一步，首先我們把所有的字母都建在一棵樹里，也就是字典樹存下所有的名字，ans =（字典樹節(jié)點數(shù)-1）* 2 + 名字?jǐn)?shù) - 最長的名字 ? ??
下面分步理解這個式子，節(jié)點數(shù)-1是因為字典樹的根節(jié)點沒有字母，*2是因為假設(shè)每一個字母增加上去又刪除了，+名字?jǐn)?shù) 是因為每個名字都要輸出一下，輸出算一步，-最長名字長度，是因為最后一個名字是不用再打印機(jī)上刪除的，我們選擇一個最每一長的這樣能達(dá)到步驟最少。然后在整體理解下，在一棵樹上，每一個節(jié)點都是一棵子樹的樹根，對于每一棵樹，他的根節(jié)點的字母只要被增加一次刪除一次就行了（最后的不用刪除）。這樣就可以很好的理解答案為什么是

ans = T_n * 2 + n - maxl 了。

#include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct Tree {Tree *next[26]; }Tree;Tree root; int sum;void Buid_Tree(char *str) {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){sum ++;q = (Tree *)malloc(sizeof(root));for(int j = 0 ;j < 26 ;j ++)q -> next[j] = NULL;p -> next[id] = q;}p = p -> next[id];} }int main () {int n ,i;char str[55];while(~scanf("%d" ,&n)){for(sum = 0 ,i = 0 ;i < 26 ;i ++)root.next[i] = NULL;int maxl = 0;for(i = 1 ;i <= n ;i ++){scanf("%s" ,str);if(maxl < strlen(str)) maxl = strlen(str);Buid_Tree(str);}printf("%d\n" ,sum * 2 + n - maxl);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu3460 字典树（打印机）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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