用深度优先搜索算法解决USACO 3.3.3 Zero Sum问题

问题描述：输入一个数N，给你三个运算符： ，-，空格；空格表示把两个数连起来比如：“2 3”就等同于23；问你有1到N（N < 9）每个数之间有一个运算符，要你输出所有计算结果为0的情况。解决方案：我

问题描述：

输入一个数N，给你三个运算符： ，-，空格；空格表示把两个数连起来比如：“2 3”就等同于23；问你有1到N（N < 9）每个数之间有一个运算符，要你输出所有计算结果为0的情况。

解决方案：

我们可以使用深度优先搜索算法进行遍历。首先我们定义一个sum变量，存储现有计算出的值，再定义一个left记录扫描到的最后一个数的值，step表示扫描到的数字。递归关系如下图所示：

![]()

判断是否满足条件时别忘了判断时要给sum加left。即sum left0。

代码实现：

```c

include

include

include

include

include

using namespace std;

int N;

int dfs(int sum, int step, int left, string print){

if(stepN){

if(sum left 0){

cout << print << endl;

return 0;

}

else

return 0;

}

if(left<0)

dfs(sum,step 1,left*10-step-1,print ' ' (char)(step 1 '0'));

else

dfs(sum,step 1,left*10 step 1,print ' ' char(step 1 '0'));

dfs(sum left,step 1,step 1,print ' ' char(step 1 '0'));

dfs(sum left,step 1,0-step-1,print '-' char(step 1 '0'));

}

int main(){

freopen("","r",stdin);

freopen("zerosum.out","w",stdout);

scanf("%d",N);

dfs(0,1,1,"1");

return 0;

}

```

本人比较懒，在这道题中没有使用任何优化剪枝，结果运算结果居然只要0ms！！！估计usaco出了点小问题。