poj 1950 Dessert（dfs枚举,模拟运算过程）

/*

这个代码运行的时间长主要是因为每次枚举之后都要重新计算一下和的值！

如果要快的话，应该在dfs，也就是枚举的过程中计算出前边的数值（这种方法见第二个代码），直到最后，这样不必每一次枚举都要从头再算一遍值！

*/

1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 char ch[20];
 8 char sign[3]={'+', '-', '.'}; 
 9 int n, cnt;
10 int num[20];
11 int signNum[200];
12 
13 void dfs(int u){
14     if(u==n){
15        if(signNum['+']==n-1 || signNum['+']+signNum['.']==n-1 || signNum['.']==n-1 || signNum['-']==n-1) return;
16        for(int i=1; i<n; ++i){           
17                num[i]=i;
18                if(ch[i]=='.'){
19                  int s=i, v=i;
20                  while(i<n && ch[i]=='.'){
21                      if(i+1>9)
22                       s=s*100+(++i);
23                     else s=s*10+(++i);
24                  }
25                  if(s>10000) return ;//非得加上这句话....然后就幸运的过了！
26                  num[v]=s;
27                  --i;
28             }
29        }
30        num[n]=n;
31        int s=num[1];
32        for(int i=1; i<n; ++i)
33              if(ch[i]!='.'){
34                if(ch[i]=='+') s+=num[i+1];
35                else s-=num[i+1];
36           }
37        if(s==0){
38                ++cnt;
39                if(cnt<=20){
40                    for(int i=1; i<n; ++i)
41                       printf("%d %c ", i, ch[i]);
42                    printf("%d\n", n);
43                }
44        }
45        return;
46      }
47     for(int i=0; i<3; ++i){
48         ch[u]=sign[i];
49         ++signNum[sign[i]];
50         dfs(u+1);
51         --signNum[sign[i]];
52     }
53 }
54 
55 int main(){
56     while(scanf("%d", &n)!=EOF){
57         cnt=0;
58         dfs(1);
59         printf("%d\n", cnt);
60     }
61     return 0;
62 } 

 /*

清晰的思路，清晰的代码.....T^T!

*/

1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 char sign[3]={'+', '-', '.'};
 7 int n, cnt;
 8 char ch[20];
 9 int dir[2]={10, 100};
10 
11 
12 //pre记录的是'+' 或者是 '-'的左边的运算值， nowI记录的是其右边的值 
13 void dfs(char chPre, int pre, int nowI, int cur){
14     if(cur==n){
15         int s=-1;
16         if(chPre=='+')
17             s=pre+(nowI*dir[cur/10]+cur);
18         else if(chPre=='-')
19               s=pre-(nowI*dir[cur/10]+cur);
20         //如果chPre=='.' 说明整个式子中不存在运算符号+或者-， 那最终的结果一定不是0 
21         if(s==0){
22             ++cnt;
23             if(cnt<=20){
24                 for(int i=1; i<n; ++i)
25                     printf("%d %c ", i, ch[i]);
26                 printf("%d\n", n);
27             }
28         }
29         return ;
30     }
31     for(int i=0; i<3; ++i){
32         ch[cur]=sign[i];
33         if(ch[cur]!='.'){
34             if(chPre=='+')
35                 dfs(ch[cur], pre+(nowI*dir[cur/10]+cur), 0, cur+1);
36             else if(chPre=='-')
37                 dfs(ch[cur], pre-(nowI*dir[cur/10]+cur), 0, cur+1);
38             else dfs(ch[cur], pre*dir[cur/10]+cur, 0, cur+1);
39         }
40         else{
41             //之前出现了运算符，当前不是运算符 
42             if(chPre=='+' || chPre=='-')//一直累计nowI的值 
43                 dfs(chPre, pre, nowI*dir[cur/10]+cur, cur+1);
44             else //如果之前没有出现过运算符+或者-，一直累计pre的值 
45                 dfs(chPre, pre*dir[cur/10]+cur, 0, cur+1);
46         }
47     }
48 }
49 
50 int main(){
51     while(scanf("%d", &n)!=EOF){    
52         cnt=0;
53         dfs(' ', 0, 0, 1);
54         printf("%d\n", cnt);
55     } 
56     return 0;
57 }