該題題意是求給定的字符串集用一個打字機來打出所有的字符串（最后一個），順序可以打亂，每次操作可以向打字機的末尾添加一個字符刪除一個字符以及打印一個單詞。這里有一個很強大的想法，那就是先假設每個單詞都打印出來起消耗為 sumlenth * 2 + N，在統(tǒng)計所有的相同的字符數(shù) M， 然后得到最長的一個單詞的長度L，把這個單詞的放在最后打印，最后答案就是 sumlen * 2 + N - M.

　　代碼如下：

1 #include <cstdlib>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5
6 struct Node
7 {
8 int cnt;
9 Node *child[26];
10 };
11
12 inline Node *init( )
13 {
14 Node *p = new Node;
15 p->cnt = -1;
16 memset( p->child, 0, sizeof( p->child ) );
17 return p;
18 }
19
20 inline bool getint( int &t )
21 {
22 char c;
23 int f = 1;
24 while( c = getchar(), ( c < '0' || c > '9' ) && c != '-' )
25 if( c == EOF ) return false;
26 if( c == '-' ) f = -1;
27 else t = c - '0';
28 while( c = getchar(), c >= '0' && c <= '9' )
29 t = t * 10 + c - '0';
30 return true;
31 }
32
33 inline void getstr( char *s )
34 {
35 char c;
36 int p = 0;
37 while( c = getchar(), c == ' ' || c == '\n' ) ;
38 s[p++] = c;
39 while( c = getchar(), c != ' ' && c != '\n' )
40 s[p++] = c;
41 s[p] = '\0';
42 }
43
44 inline void insert( Node *p, char *in )
45 {
46 int dx = *in - 'a';
47 if( *in )
48 {
49 if( p->child[dx] == NULL )
50 p->child[dx] = init();
51 p->child[dx]->cnt++;
52 insert( p->child[dx], in + 1 );
53 }
54 }
55
56 inline void getsum( Node *p, int &cnt )
57 {
58 for( int i = 0; i < 26; ++i )
59 {
60 if( p->child[i] )
61 {
62 cnt += p->child[i]->cnt;
63 getsum( p->child[i], cnt );
64 }
65 }
66 free( p );
67 }
68
69 int main()
70 {
71 int N;
72 while( getint( N ) )
73 {
74 Node *r = init();
75 char str[55];
76 int ans = 0, cnt = 0, maxlen = -0x7fffffff;
77 for( int i = 0; i < N; ++i )
78 {
79 getstr( str );
80 int len = strlen( str );
81 maxlen = maxlen > len ? maxlen : len;
82 ans += len;
83 insert( r, str );
84 }
85 getsum( r, cnt );
86 printf( "%d\n", ( ans - cnt ) * 2 + N - maxlen );
87 }
88 }

總結(jié)

以上是生活随笔為你收集整理的HDU-3460 Ancient Printer 字典树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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