- 31.33%
- 1000ms
- 131072K
请对于下面式子进行填空，填入加减乘，使这个表达式成立。
1空 2 空 3 空 4 空 5 空 6 空 7 空 8 空 9 空 10 = 0
请输出一共有多少种方案可以使得表达式成立。
这道题看到这道题的时候知道这道应该是道dfs的题目，但是由于刚刚接触dfs算法，没有掌握好，所以打算用暴力解决，结果发现我漏了一种情况：运算符的优先级关系，也就是当空格填的时候应该先算再算+-。所以一直WA了好几次。
言归正传，dfs要考虑到运算符优先级的关系，所以当遇到乘*的时候应该先将前个数字乘起来再和前面的和进行加减运算。弄懂这一点就非常简单了，只要再确立边界条件cnt==11就可以写出，附上蒟蒻的AC代码
#include <iostream>
using namespace std;
int num[11] = {0,1,2,3,4,5,6,7,8,9,10},t = 0;
int a_b(int a,int c,int b){
if(c=='+')
return a+b;
else
return a-b;
}
void dfs(int a,char c,int b,int cnt){
if(cnt==11){
if(a_b(a,c,b)==0){
t++;
}
return;
}
dfs(a_b(a,c,b),'+',num[cnt],cnt+1);
dfs(a_b(a,c,b),'-',num[cnt],cnt+1);
dfs(a,c,b*num[cnt],cnt+1);
}
int main()
{
dfs(0,'+',1,2);
cout << t;
return 0;
}
