HDU2266 How Many Equations Can You Find(DFS)

题目链接

题意:在一组数中添加加号或减号使结果等于指定的数。

#include<bits/stdc++.h>
using namespace std;
long long n, ans, len;
char s[20];
void dfs(long long x, long long sum){ //第x位 当前和sum
    if(x == len){
        if(sum == n)
            ans++;
        return;
    }
    long long k = 0;
    for(int i = x; i < len; i++){
        k = k*10 + s[i] -'0';
        dfs(i+1, sum+k);
        if(x)
            dfs(i+1, sum-k);
    }
}
int main(){
    while(scanf("%s %lld", s, &n) != EOF){
        ans = 0;
        len = strlen(s);
        dfs(0, 0);
        cout << ans << endl;
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with DFS