本文主要是介绍10400 -Game Show Math，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题的话利用了暴力深搜，尽管给了20S，但是这样还会超时，所以就需要利用回溯进行减枝，因为是DFS，所以用一个数组vis[i][j]记录是否在状态i时候取到过j值，如果取到过的话，那么直接回溯（往后搜索已经没有意义了，之前到达这个状态的时候是无法得到结果的）
还有需要注意的地方就是题目的要求，每一步的结构都在(-32000,32000)之间，所以需要一步判断，如果在这个范围外直接回溯
最后一点就是由于包含了除法，所以记得要考虑除数为0的情况，否则会RE
网上还有人利用DP思想做的，不过我还没学到这个专题，所以先不做过多的分析了
减枝前后的时间从TEL减到了0.48s，可以看出正确的减枝对程序优化的巨大作用
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100 + 10
#define MAXD 100000
int n,m,ok;
int array[N];
char oper[N];
int vis[N][MAXD];
void solve(int u,int sum){if(ok) return ;if(sum > 32000 || sum < -32000) return ;if(u == n && sum == m){ok = 1;return ;}if(vis[u][sum + 32000]) return ;vis[u][sum + 32000] = 1;if(u == n) return ;oper[u] = '+'; solve(u + 1, sum + array[u]);if(ok) return ;oper[u] = '-'; solve(u + 1, sum - array[u]);if(ok) return ;oper[u] = '*'; solve(u + 1, sum * array[u]);if(ok) return ;if(array[u] != 0){oper[u] = '/'; solve(u + 1, sum / array[u]);if(ok) return ;}
}
int main(){int T;scanf("%d",&T);for(int Case = 1; Case <= T; Case ++){ok = 0;memset(vis,0,sizeof(vis));scanf("%d",&n);for(int i = 0; i < n ; i++)scanf("%d",&array[i]);scanf("%d",&m);solve(1,array[0]);if(ok)for(int i = 0; i < n ; i++){printf("%d",array[i]);if(i < n - 1) printf("%c",oper[i + 1]);if(i == n - 1) printf("=%d",m);}else printf("NO EXPRESSION");printf("\n");}return 0;
}
这篇关于10400 -Game Show Math的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
