hdu 3460 Ancient Printer

点击打开链接hdu3640

思路：字典树

分析：
1 题目要求的是给定n个字符串，现在有一台的打印机有三种操作“取字符”，“删除最后一个字符”，“打印当前单词”，问最少需要几次的操作（最后一个单词不用删除）。
2 要最少的次数，那么就是使得最后一个单词必须是所有单词中的最长的，所以这里需要涉及到对二维数组的排序利用qsort从小到大；
3 如果两个单词有相同的公共前缀那么肯定是可以减少输入的次数，所以在建字典树的时候应该在节点里面用一个flag标记当前的字符是否被取过，还有要几下以当前的单词为前缀的字符串的个数count。
4 几下了以当前字符串为前缀的字符串的个数的时候，那么我们在具体查找的时候就是判断当前的字符是否被取过，如果没被取过那么标记为取过并ans++；每一次都要把当前字符的count--，当count = 0并且不是最后一个单词的时候就要开始删除所以这个时候ans++；

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

#define MAXN 1000010
#define MAX 60
#define N 30

int cnt , n;
int ans;
char words[10010][MAX];
struct Trie{
   int count;
   bool flag;
   Trie *child[N];
}trie[MAXN];
Trie *root;

/*自定义的函数*/
int cmp(const void *str1 , const void *str2){
    return strlen((char*)str1) - strlen((char*)str2);
}

/*字典树的空间的分配*/
Trie* newTrie(){
   trie[cnt].count = 0;
   trie[cnt].flag = false;
   for(int i = 0 ; i < N ; i ++)
     trie[cnt].child[i] = NULL;
   return &trie[cnt++];
}

/*字典树的插入*/
void insert(char *str){
    Trie *s = root;
    int len = strlen(str);
    for(int i = 0 ; i < len ; i++){
       int num = str[i]-'a';
       if(s->child[num] == NULL)
         s->child[num] = newTrie();
       s = s->child[num];
       s->count++;/*这里自增加1*/
    }
}

/*字典树的查找*/
void search(char *str , int j){
    Trie *s = root;
    int len = strlen(str);
    for(int i = 0 ; i < len ; i++){
       int num = str[i]-'a';
       s = s->child[num];
       if(s->flag == false){
         ans++;
         s->flag = true;
       }
       s->count--;/*这个地方一定要减1，不然就是WA*/
       if(s->count == 0 && j != n-1)
         ans++;
    }
    ans++;/*每一个单词都要打印就是加1*/
}

int main(){
   while(scanf("%d" , &n) != EOF){
       cnt = 0;
       root = newTrie();
       for(int i = 0 ; i < n ; i++){
          scanf("%s" , words[i]);
          insert(words[i]);
       }
       qsort(words , n , sizeof(words[0]) , cmp);/*按照长度排序*/
       ans = 0;
       for(int i = 0 ; i < n ; i++)
          search(words[i] , i);
       printf("%d\n" , ans);
   }
   return 0;
}