USACO Letter Game

这道题的难度比较低。USACO给出的题解使用DFS+Tire解决这个问题的。思路是先构造单词串，然后再用Tire检查单词是否在辞典中。
本人采用了另一种方法：
在读入字典的时候，剔除明显不符合条件的单词，然后枚举得出分数最高的单词（或词组）就可以了。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 char word[40000][10];
006 int wlen[40000];
007 int wcnt[40000][30];
008 int wvalue[40000];
009 long total_word;
010
011 int value[30];
012 int max = 0;
013 int pair[40000][2];
014 long paircnt = 0;
015 char ans[40000][15];
016 long anscnt;
017
018 char str[10];
019 int strcnt[30] = {};
020 int maxlen;
021
022 int valid(char *tmp)
023 {
024     int i;
025     static int ccnt[30];
026     memset(ccnt,0,sizeof(ccnt));
027     for(;*tmp;tmp ++)
028     {
029         ccnt[*tmp - 'a'] ++;
030     }
031     for(i = 0;i <= 'z' - 'a';i ++)
032     {
033         if(ccnt[i] > strcnt[i])    return 0;
034     }
035     return 1;
036 }
037
038 void countchar(char *tmp,int *cntarr)
039 {
040     for(;*tmp;tmp ++)
041         cntarr[*tmp - 'a'] ++;
042 }
043
044 int calcvalue(char *tmp)
045 {
046     int v = 0;
047     for(;*tmp;tmp ++)
048         v += value[*tmp - 'a'];
049     return v;
050 }
051
052 void read_dict()
053 {
054     FILE *dict;
055     dict = fopen("lgame.dict","r");
056     long i;
057     char tmp[10];
058     for(i = 0;i < 40000;)
059     {
060         fscanf(dict,"%s",tmp);
061         if(strcmp(tmp,".") == 0)    break;
062         if(strlen(tmp) <= maxlen && valid(tmp))
063         {
064             memcpy(word[i],tmp,sizeof(tmp));
065             wlen[i] = strlen(tmp);
066             countchar(tmp,wcnt[i]);
067             wvalue[i] = calcvalue(tmp);
068             i ++;
069         }
070     }
071     total_word = i;
072     fclose(dict);
073    
074     /*for(i = 0;i < total_word;i ++)
075     {
076         printf("%d %d %s\n",wlen[i],wvalue[i],word[i]);
077     }*/
078 }
079
080 void init_value()
081 {
082     value['a' - 'a'] = 2;
083     value['s' - 'a'] = 1;
084     value['d' - 'a'] = 4;
085     value['f' - 'a'] = 6;
086     value['g' - 'a'] = 5;
087     value['h' - 'a'] = 5;
088     value['j' - 'a'] = 7;
089     value['k' - 'a'] = 6;
090     value['l' - 'a'] = 3;
091     value['q' - 'a'] = 7;
092     value['w' - 'a'] = 6;
093     value['e' - 'a'] = 1;
094     value['r' - 'a'] = 2;
095     value['t' - 'a'] = 2;
096     value['y' - 'a'] = 5;
097     value['u' - 'a'] = 4;
098     value['i' - 'a'] = 1;
099     value['o' - 'a'] = 3;
100     value['p' - 'a'] = 5;
101     value['z' - 'a'] = 7;
102     value['x' - 'a'] = 7;
103     value['c' - 'a'] = 4;
104     value['v' - 'a'] = 6;
105     value['b' - 'a'] = 5;
106     value['n' - 'a'] = 2;
107     value['m' - 'a'] = 5;
108    
109 }
110
111 void read_str()
112 {
113     scanf("%s",str);
114     //puts(str);
115     maxlen = strlen(str);
116     countchar(str,strcnt);
117 }
118
119 void solve_single()
120 {
121     long i;
122     for(i = 0;i < total_word;i ++)
123         if(wvalue[i] > max)    max = wvalue[i];
124 }
125
126 int check(int *cnt1,int *cnt2)
127 {
128     int i;
129     for(i = 0;i <= 'z' - 'a';i ++)
130     {
131         if(cnt1[i] + cnt2[i] > strcnt[i])    return 0;
132     }
133     return 1;
134 }
135
136 void solve_pair()
137 {
138     long i,j;
139     for(i = 0;i < total_word;i ++)
140         for(j = i;j < total_word;j ++)
141         {
142             if(wvalue[i] + wvalue[j] >= max && check(wcnt[i],wcnt[j]))
143             {
144                 if(wvalue[i] + wvalue[j] > max)
145                 {
146                     max = wvalue[i] + wvalue[j];
147                     paircnt = 1;
148                     pair[0][0] = i;
149                     pair[0][1] = j;
150                 }
151                 else if(wvalue[i] + wvalue[j] == max)
152                 {
153                     pair[paircnt][0] = i;
154                     pair[paircnt][1] = j;
155                     paircnt ++;
156                 }
157             }
158         }
159 }
160
161 int cmp(const void *a,const void *b)
162 {
163     return (int)strcmp((char *)a,(char *)b);
164 }
165
166 void sort()
167 {
168     long i;
169     for(i = 0;i < paircnt;i ++)
170     {
171         strcpy(ans[anscnt],word[pair[i][0]]);
172         strcat(ans[anscnt]," ");
173         strcat(ans[anscnt],word[pair[i][1]]);
174         anscnt ++;
175     }
176     for(i = 0;i < total_word;i ++)
177     {
178         if(wvalue[i] == max)    strcpy(ans[anscnt ++],word[i]);
179     }
180     qsort(ans,anscnt,15,cmp);
181     printf("%d\n",max);
182     for(i = 0;i < anscnt;i ++)
183     {
184         puts(ans[i]);
185     }
186 }
187
188 int main()
189 {
190     freopen("lgame.in","r",stdin);
191     freopen("lgame.out","w",stdout);
192     init_value();
193     read_str();
194     read_dict();
195     solve_single();
196     solve_pair();
197     sort();
198     return 0;
199 }