单纯的字典树，有规律可循。最小次数=节点*2-最长的那条链+n个链。。可以先想想假设最后那个单词也删除的话，那么每个节点的单词都会先打出，然后删除，所以所有的节点*2.但是题目的意思是最后那个单词不删除，所以要保持最小次数，那么最后那个单词必定是最长的。所以要将所有节点*2-最长链。
代码：
| #include<iostream> #include<cstring> using namespace std; typedef struct trie { trie *next[26];//26个分枝节点代表26个单词 }zidian; zidian root[100000];//先创建10万个节点，以备题目要求输入多组测试 int count=0,h=0; int Creattrie(char* str) { // cout<<"hah"<<endl; zidian *p=&root[h],*q; int len=strlen(str); for(int i=0;i<len;i++) { int id=str[i]-'a'; // cout<<"hah"<<endl; if(p->next[id]==NULL) { q=(zidian*)malloc(sizeof(zidian)); for(int j=0;j<26;j++) q->next[j]=NULL; count++; p->next[id]=q; p=p->next[id]; } else p=p->next[id]; } return count; } int main(void) { int jds=0,max=0,len,n,sum; char word[101]; while(cin>>n) { h++; max=0; count=0; sum=n; getchar(); while(n--) { gets(word); jds=Creattrie(word); // cout<<"jhhah"<<endl; len=strlen(word); max=max>len? max:len; } // cout<<jds<<" "<<max<<" "<<sum<<endl; cout<<jds*2-max+sum<<endl; } return 0; } |