HDU4403 DFS

題意:一連の数字を与え、これらの数字時計に「+」または「=」を挿入して両側を等しくする.
考え方:まずこの文字列の任意の2つの位置の表示の数の大きさを暴力します...
次に等号の位置を列挙し,両側にdfsを行う.
(dfsは最初は本当に考えられなかった.の参考にしてください.http://blog.csdn.net/kk303/article/details/8008058)


View Code

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<algorithm>

 4 using namespace std;

 5 const int maxn = 24;

 6 char a[ maxn ];

 7 int num[ maxn ][ maxn ];

 8 int ans,len;

 9 int get_num( int x,int y ){

10     int sum=0;

11     int tmp=1;

12     for( int i=y;i>=x;i-- ){

13         sum+=( ( a[i]-'0' )*tmp );

14         tmp*=10;

15     }

16     return sum;

17 }

18 void dfs_right( int y,int pre_sum,int now_sum,int mid ){

19     if( y>len ){

20         if( pre_sum==now_sum )

21             ans++;

22         return ;

23     }

24     for( int k=y;k<=len;k++ ){

25         dfs_right( k+1,pre_sum,now_sum+num[y][k],mid );

26     }

27 }

28 void dfs_left( int x,int sum,int mid ){

29     //if( sum>num[ mid ][ len ] )

30         //return ;//        ！！！

31     if( x>=mid ) {

32         //if( mid==6 )

33             //printf("sum:%d
",sum);//it is just for test

34         dfs_right( mid,sum,0,mid );//pos,pre_sum,now_sum,mid

35     }

36     for( int k=x;k<mid;k++ )

37         dfs_left( k+1,sum+num[x][k],mid );

38 }

39 int main(){

40     while( scanf("%s",a+1)!=EOF ){

41         if( a[1]=='E' ){

42             break;

43         }

44         len=strlen( a+1 );

45         memset( num,0,sizeof( num ) );

46         for( int i=1;i<=len;i++ ){

47             for( int j=i;j<=len;j++ ){

48                 num[ i ][ j ]=get_num( i,j );

49             }

50         }//        i，j     

51         ans=0;

52         for( int mid=2;mid<=len;mid++ ){//       

53             dfs_left( 1,0,mid );//pos,now_num,mid

54         }

55         printf("%d
",ans);

56     }

57     return 0;

58 }