HDU 2011 How Many Equations Can You Find ——————DFS

旧城等待， 2022-05-14 11:22 136阅读 0赞

# How Many Equations Can You Find #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 1477 Accepted Submission(s): 990**

Problem Description

Now give you an string which only contains 0, 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9.You are asked to add the sign ‘+’ or ’-’ between the characters. Just like give you a string “12345”, you can work out a string “123+4-5”. Now give you an integer N, please tell me how many ways can you find to make the result of the string equal to N .You can only choose at most one sign between two adjacent characters.

Input

Each case contains a string s and a number N . You may be sure the length of the string will not exceed 12 and the absolute value of N will not exceed 999999999999.

Output

The output contains one line for each data set : the number of ways you can find to make the equation.

Sample Input

123456789 3 
       
        
    
    21 1

Sample Output

18 
       
        
    
    1

--------------------

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n;
    ll l,len;
    ll cnt;
    char str[15];
    
    void DFS(int l,ll sum)// l记录当前所用的字符个数，sum传递的是前 [0,l-1] 个字符经过加减得到的值 
    {
        if(l==len && sum==n)//当字符串全部用完  并且得到的值等于n 时才满足条件 
        {
            cnt++  ;  
            return ;//一个递归结束 
        }
        ll ans=0;// ans 保存的是以后的值 
        for(int i=l;i<len;i++)
        {
            ans=ans*10+str[i]-'0';
            DFS(i+1,sum+ans);
            if(l)
                DFS(i+1,sum-ans);//第一个数字前面不能是减号 
         } 
    }
    
    int main()
    {
        while(~scanf("%s %lld",str,&n))
        {
              len=strlen(str);
              cnt=0;//记录有多少种方式   
              DFS(0,0);
              printf("%d\n",cnt);
        }
        return 0;
    }
    
    /*
    
    对于任意一串数字，我们可以在其中：
        添加 +
        添加 -
        不添加
    
    这一串数字的长度不超过11
    
    复杂度应该是  O(3^11)
    
    
    
    
    
    DFS(l,sum)
    
    1234 10
    
    DFS(0,0)    ->DFS(1,1)//    l=0  sum=0;
                ->DFS(1,12)
                ->DFS(1,123)
                ->DFS(1,1234)//对于所有的数字全部用完的情况，都可以直接判断结果是否等于N,然后结束   
    
    DFS(1,1)    ->DFS(2,1+2)
                ->DFS(2,1-2)
                ->DFS(2,1+23)
                ->DFS(2,1-23)
                ->DFS(2,1+234)//对于所有的数字全部用完的情况，都可以直接判断结果是否等于N,然后结束
                ->DFS(2,1-234)//对于所有的数字全部用完的情况，都可以直接判断结果是否等于N,然后结束
    
    DFS(1,12)   ->DFS(2,12+3)
                ->DFS(2,12-3)
                ->DFS(2,12+34)//对于所有的数字全部用完的情况，都可以直接判断结果是否等于N,然后结束
                ->DFS(2,12-34)//对于所有的数字全部用完的情况，都可以直接判断结果是否等于N,然后结束
    
    DFS(1,123)  ->DFS(2,123+4)
                ->DFS(2,123-4)
    
    DFS(2,1+2)  ->DFS(3,1+2+3)
                ->DFS(3,1+2-3)
                ->DFS(3,1+2+34)
                ->DFS(3,1+2-34)
    
    DFS(2,1-2)  ->DFS(3,1-2+3)
                ->DFS(3,1-2-3)
                ->DFS(3,1-2+34)
                 ->DFS(3,1-2-34)
    
    DFS(2,1+23) ->..... 
    DFS(2,1-23) ->.....
    DFS(2,1+234)->.....
    DFS(2,1-234)->.....
    
    DFS(3,...)->......
    DFS(3,...)->......
    DFS(3,...)->......
    DFS(3,...)->......
    
    DFS(4,...)->......
    DFS(4,...)->......
    DFS(4,...)->......
    DFS(4,...)->......
    
    */