hdu 4192

发布时间:2016-12-9 15:59:37 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu 4192",主要涉及到hdu 4192方面的内容,对于hdu 4192感兴趣的同学可以参考一下。

dfs全排列  加  模拟计算  #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #define maxn 10010 using namespace std; bool vis[10]; int value[10], result, n, now[10],top; char expr[100]; int check(int l, int r) { if(l > r) return 0; int cnt = 0,p = -1,flag = 0; for(int i = l; i <= r; i++) if(expr[i] == '(') ++cnt; else if(expr[i] == ')') --cnt; else if((expr[i] == '+' || expr[i] == '-') && !cnt) flag = 1, p = i; else if((expr[i] == '*') && !cnt && !flag) p = i; if( p == -1 ) { if( l == r ) { return now[top++]; } return check(l+1, r-1); } switch(expr[p]) { case '+': return check(l,p-1) + check(p+1,r); case '-': return check(l,p-1) - check(p+1,r); case '*': return check(l,p-1) * check(p+1,r); } return 0; } int dfs(int cur) { if( cur == n ) { top = 0; int len = strlen(expr); if(check(0, len-1) == result) return 1; // printf("%d\n",check(0,len-1)); } for(int i = 0; i < n; i++) { if( !vis[i] ) { vis[i] = true; now[cur] = value[i]; if(dfs(cur+1)) return 1; vis[i] = false; } } return 0; } int main() { while( scanf("%d",&n) == 1 ) { if(n == 0) { scanf("%d",&result); if(result == 0) break; } for(int i = 0; i < n; i++) scanf("%d",&value[i]); scanf("%d",&result); scanf("%s",expr); int flag = 0; for(int i = 0; i < n; i++) { memset(vis, false, sizeof(vis)); vis[i] = true; now[0] = value[i]; if(dfs(1)) { flag = 1; break; } vis[i] = false; } if( flag ) puts("YES"); else puts("NO"); } return 0; } 使用stl中的全排列函数 #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #define maxn 10010 using namespace std; int value[10], result, n, top; char expr[100]; int check(int l, int r) { if(l == r) return value[top++]; int cnt = 0,p = -1,flag = 0; for(int i = l; i <= r; i++) if(expr[i] == '(') cnt++; else if(expr[i] == ')') cnt--; else if((expr[i] == '+' || expr[i] == '-') && !cnt) flag = 1, p = i; else if((expr[i] == '*') && !cnt && !flag) p = i; if( p == -1 ) return check(l+1, r-1); switch(expr[p]) { case '+': return check(l,p-1) + check(p+1,r); case '-': return check(l,p-1) - check(p+1,r); case '*': return check(l,p-1) * check(p+1,r); } return 0; } int main() { while( scanf("%d",&n) == 1 ) { if(n == 0) { scanf("%d",&result); if(result == 0) break; } for(int i = 0; i < n; i++) scanf("%d",&value[i]); scanf("%d",&result); scanf("%s",expr); int flag = 0; int len = strlen(expr); sort(value, value+n); do { top = 0; if(check(0, len-1) == result) { flag = 1; break; } }while(next_permutation(value, value+n)); if( flag ) puts("YES"); else puts("NO"); } return 0; }

上一篇:UIScrollView--UIPageControl
下一篇:A - 一二三

相关文章

关键词: hdu 4192

相关评论