首页 > 代码库 > uva 10400 Game Show Math (填合适的运算符)
uva 10400 Game Show Math (填合适的运算符)
看到这种填合适的运算符之类的题目,第一感觉就是用dfs来枚举递归。
但邮箱道题目算法设计里面那么大的数据,想到有可能会超时。
用最直白的简单的方法dfs一遍后交上,超时。
——需要判重和边界结束条件。
在所有能剪断的地方痛下狠手,狂加特判+return;
然后就炒鸡快了
#include<iostream> #include<cstring> #include<cstdio> #define ADD 32000 using namespace std; int arr[120], target, p; char route[120]; bool flag, vis[102][32002*2+2]; inline bool isOk(int m, int cur) { return m>=-32000&&m<=32000 && !vis[cur][m+ADD]; } void dfs(int cur, int sum) { if(flag)return ; if(cur==p) { if(sum==target) flag=true; return; } if(flag) return; for(int i=0; i<4; ++i) { if(i==0&&isOk(sum+arr[cur], cur)) { vis[cur][sum+arr[cur]+ADD] = true; route[cur-1]='+'; dfs(cur+1, sum+arr[cur]); } else if(i==1 && isOk(sum-arr[cur], cur)) { vis[cur][sum-arr[cur]+ADD] = true; route[cur-1]='-'; dfs(cur+1,sum-arr[cur]); } else if(i==2 && isOk(sum*arr[cur], cur)) { vis[cur][sum*arr[cur]+ADD] = true; route[cur-1]='*'; dfs(cur+1,sum*arr[cur]); } else if(i==3 && arr[cur]!=0 && isOk(sum/arr[cur], cur)) { vis[cur][sum/arr[cur]+ADD] = true; route[cur-1]='/'; dfs(cur+1,sum/arr[cur]); } if(flag)return; } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&p); for(int i=0; i<p; ++i) scanf("%d",&arr[i]); scanf("%d",&target); memset(vis, false, sizeof(vis)); vis[0][arr[0]+ADD] = true; flag=false; dfs(1, arr[0]); if(flag) { printf("%d",arr[0]); for(int i=1; i<p; ++i) { printf("%c%d",route[i-1],arr[i]); } printf("=%d\n",target); } else printf("NO EXPRESSION\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。