hdu 4403 爆搜

 1 //1004
 2 #include<stdio.h>
 3 #include<iostream>
 4 #include<map>
 5 #include<set>
 6 #include<algorithm>
 7 #include<string.h>
 8 #include<stdlib.h>
 9 using namespace std;
10 
11 int a[20];
12 int n;
13 
14 bool solve(int s1,int s2,int t)
15 {
16     int aa,b;
17     aa=0;
18     b=0;
19     int temp=a[1];
20     int p=1;
21     for(int i=1;i<t;i++)
22     {
23         if(s1&(1<<(i-1)))
24         {
25             aa+=temp;
26             temp=a[i+1];
27         }
28         else
29         {
30             temp*=10;
31             temp+=a[i+1];
32         }
33     }
34     aa+=temp;
35     temp=a[t+1];
36     for(int i=t+1;i<n;i++)
37     {
38 
39         int qq=i-t-1;
40         if(s2&(1<<qq))
41         {
42             b+=temp;
43             temp=a[i+1];
44         }
45         else
46         {
47             temp*=10;
48             temp+=a[i+1];
49         }
50     }
51     b+=temp;
52     if(aa==b)return true;
53     else return false;
54 }
55 char str[30];
56 int main()
57 {
58     //freopen("D.in","r",stdin);
59    // freopen("D.out","w",stdout);
60     while(scanf("%s",&str))
61     {
62         if(strcmp(str,"END")==0)break;
63         int ans=0;
64         n=strlen(str);
65         for(int i=0;i<n;i++)
66            a[i+1]=str[i]-‘0‘;
67         for(int i=1;i<n;i++)
68         {
69             int t1=(1<<(i-1));
70             int t2=(1<<(n-i-1));
71             for(int s1=0;s1<t1;s1++)
72               for(int s2=0;s2<t2;s2++)
73                 if(solve(s1,s2,i))
74                    ans++;
75         }
76         printf("%d\n",ans);
77     }
78     return 0;
79 }

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<map>
 7 #include<queue>
 8 #include<stack>
 9 #define ll long long
10 #define oo 1000000000
11 #define pi acos(-1)
12 using namespace std; 
13 ll ans,T[20][20],len,mid;
14 char s[20];
15 void dfs2(int i,ll data,ll pre)
16 {
17      int k;
18      if (i>len)
19      {
20           if (data==pre) ans++;
21           return ;
22      }
23      for (k=i;k<=len;k++)
24           dfs2(k+1,data+T[i][k],pre);
25      return;
26 }
27 void dfs1(int i,ll data)
28 {
29      int k;
30      if (i>mid) dfs2(mid+1,0,data);
31      for (k=i;k<=mid;k++)
32          dfs1(k+1,data+T[i][k]);
33      return;
34 }
35 int main()
36 { 
37      int i,j,k;
38      while (gets(s+1))
39      { 
40             if (s[1]==‘E‘) break;
41             len=strlen(s+1);
42             for (i=1;i<=len;i++)
43               for (j=i;j<=len;j++)
44               {
45                     T[i][j]=0;
46                     for (k=i;k<=j;k++) T[i][j]=T[i][j]*10+s[k]-‘0‘;
47               }
48             ans=0;
49             for (mid=1;mid<len;mid++)
50                  dfs1(1,0);
51             printf("%I64d\n",ans);
52      }
53      return 0;
54 }