首页 > 代码库 > uva--10400+dfs+回溯
uva--10400+dfs+回溯
题意:
输入n个正整数和一个目标值,可以在这n个数中间填充+ - × /号进行运算,运算从左到右进行,不考虑运算符的优先性。 并且给定下面的规则:
1.填充符号时n个数的顺序不能改变。
2.填充除号的时候必须保证结果为整数。
3.每一步的结果必须在-32000~32000之间。
问是否可以求得目标值。
思路:
很显然可以用dfs+回溯来实现符号的填充,但是直接dfs是绝对会超时的(我就WA了一发);那么我们就要考虑剪枝了,这个题目可以利用状态来进行剪枝:我们记录下每一步得到的结果,如果回溯到这一步并且结果和原先的结果一致的话就可以直接返回。利用这个剪枝就可以AC啦。
还有就是每一步计算的结果都有可能为负数,为了利用数组进行判重,我们需要把结果加上50000后作为数组下标。
代码如下:
<span style="font-size:18px;">#include<iostream> #include<cstring> #include<cstdio> using namespace std; int a[110],n,flag,goal,vis[110][90000]; char ans[110]; inline int check(int a,int cur) { if(a>=-32000&&a<=32000&&!vis[cur][a+50000]) { vis[cur][a+50000]=1; return 1; } return 0; } void dfs(int cur,int sum) { if(cur==n-1) { if(sum==goal) { ans[cur]='='; for(int i=0;i<n;i++) printf("%d%c",a[i],ans[i]); printf("%d\n",goal); flag=1; } return ; } if(flag) return ; if(check(sum+a[cur+1],cur)) { ans[cur]='+'; dfs(cur+1,sum+a[cur+1]); } if(flag) return ; if(check(sum-a[cur+1],cur)) { ans[cur]='-'; dfs(cur+1,sum-a[cur+1]); } if(flag) return ; if(check(sum*a[cur+1],cur)) { ans[cur]='*'; dfs(cur+1,sum*a[cur+1]); } if(flag) return ; if(sum%a[cur+1]==0&&check(sum/a[cur+1],cur)) { ans[cur]='/'; dfs(cur+1,sum/a[cur+1]); } if(flag) return ; } int main() { int i,j,t; scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); scanf("%d",&goal); flag=0; dfs(0,a[0]); if(!flag) printf("NO EXPRESSION\n"); } return 0; }</span>
uva--10400+dfs+回溯
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。