uva 10400 Game Show Math

本文主要是介绍uva 10400 Game Show Math，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：满足表达式，用DFS记忆化搜索，把到当前运算符所得的结果记录下来，起初用回溯一直错

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;int flag,n,b[101],ans,a[101],vis[100][64001];void dfs(int sum,int deep)
{if (deep > n && sum == ans) {flag=1; return;}if (flag || deep > n || abs(sum) > 32000)return;for (int i = 1; i <= 4; i++){b[deep-1] = i;int s = 32001;if (i == 1) s = sum + a[deep];if (i == 2) s = sum - a[deep];if (i == 3)s = sum * a[deep];if (i == 4 && (sum % a[deep] == 0)) s = sum / a[deep];if (abs(s) <=32000 && vis[deep-1][s] == 0){vis[deep-1][s]=1;dfs(s,deep+1);}if (flag)return;}
}
int main()
{ int t;scanf("%d",&t);while (t--){scanf("%d",&n);for (int i = 1; i <= n; i++)scanf("%d",&a[i]);scanf("%d",&ans);flag=0;memset(vis,0,sizeof(vis));dfs(a[1],2);if (flag){for (int i =1 ; i < n; i++){printf("%d",a[i]);if (b[i] == 1)printf("+");if (b[i] == 2) printf("-");if (b[i] == 3)printf("*");if (b[i] == 4)printf("/");}printf("%d=%d\n",a[n],ans);}elseprintf("NO EXPRESSION\n");}return 0;
}

这篇关于uva 10400 Game Show Math的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---