uva 10400 Game Show Math (填合适的运算符)

看到这种填合适的运算符之类的题目，第一感觉就是用dfs来枚举递归。

但邮箱道题目算法设计里面那么大的数据，想到有可能会超时。

用最直白的简单的方法dfs一遍后交上，超时。

――需要判重和边界结束条件。

在所有能剪断的地方痛下狠手，狂加特判+return；

然后就炒鸡快了

#include
  
   
#include
   
     #include
    
      #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