UESTC OJ 1824 Judgment Day 递归搜索

这题就是写个DFS，搞定，比赛的时候没有看到N<=10,不敢暴力，因为这个的复杂度为2^n.看题一定要认真啊啊啊啊！！！！！

枚举所有的可能，每个人都有两种情况，一是spell他的名字，一个是不spell.所以一共有2^n种情况，当然，名字拼不出来就只有一种，就是不spell

.简单吧，用递归写，我一般都把递归写的叫DFS。

贴代码:

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 int n;
 4 int num[30];
 5 int pn[11][30];
 6 int max;
 7 void dfs(int x,int m)
 8 {
 9     if(x == n)
10     {
11         if(m > max) max = m;
12         return;
13     }
14     int i;
15     for(i=0; i<26; ++i)
16     {
17         if(num[i] < pn[x][i])
18             break;
19     }
20     if(i == 26)
21     {
22         for(int j = 0; j< 26; ++j)
23             num[j] -= pn[x][j];
24         dfs(x+1,m+1);
25         for(int j = 0; j< 26; ++j)
26             num[j] += pn[x][j];
27         dfs(x+1,m);
28     }
29     else
30     {
31         dfs(x+1,m);
32     }
33 }
34 int main()
35 {
36 //    freopen("in.cpp","r",stdin);
37     char a[100005],p[100005];
38     int T;
39     scanf("%d",&T);
40     for(int i=1; i<=T; ++i)
41     {
42         scanf("%s",a);
43         int len = strlen(a);
44         memset(num,0,sizeof(num));
45         memset(pn,0,sizeof(pn));
46         for(int k=0; k<len; ++k)
47         {
48             ++num[a[k]-'a'];
49         }
50         scanf("%d",&n);
51         for(int k=0; k<n; ++k)
52         {
53             scanf("%s",p);
54             len = strlen(p);
55             for(int s=0; s<len; ++s)
56             {
57                 ++pn[k][p[s]-'a'];
58             }
59         }
60         printf("Case #%d: ",i);
61         max = 0;
62         dfs(0,0);
63         printf("%d\n",max);
64     }
65     return 0;
66 }