UVA - 817 According to Bartjens 暴力 - c++编程基础

TOP

UVA - 817 According to Bartjens 暴力

2015-11-21 01:03:18 来源: 作者: 【大中小】浏览:1次

题目大意：给出一个字符串，要求你在这个字符串里面加入符号，使得结果为2000

解题思路：直接暴力

#include
   
     #include
    
      #include
     
       #define maxn 30 using namespace std; char str[maxn]; bool flag; int num[maxn], sign[maxn], len; char s[5]= " *+-"; bool judge(int num_s, int num_n) { vector
      
        Num, Sign; for(int i = 0; i < num_s; i++) Sign.push_back(sign[i]); for(int i = 0; i < num_n; i++) Num.push_back(num[i]); for(int i = 0; i < Sign.size(); i++) if(Sign[i] == 1) { Num[i + 1] *= Num[i]; Num.erase(Num.begin() + i); Sign.erase(Sign.begin() + i); i--; } int t = Num[0]; for(int i = 0; i < Sign.size(); i++) if(Sign[i] == 2) t += Num[i + 1]; else t -= Num[i + 1]; return t == 2000; } void dfs(int cur, int cur_sign, int cur_num) { if(cur == len - 1) { if(judge(cur_sign, cur_num)) { flag = true; printf(" "); for(int i = 0; i < cur_num - 1; i++) printf("%d%c", num[i], s[sign[i]]); printf("%d=\n",num[cur_num - 1]); } return; } int t = 0; for(int i = cur ; i < len - 1; i++) { if(i == cur && str[i] == '0') { num[cur_num] = 0; if(i != len - 2) { for(int j = 1; j <= 3; j++) { sign[cur_sign] = j; dfs(i + 1, cur_sign+1, cur_num+1); } } else dfs(i + 1, cur_sign, cur_num + 1); break; } t = t * 10 + str[i] - '0'; num[cur_num] = t; if(i != len - 2) { for(int j = 1; j <= 3; j++) { sign[cur_sign] = j; dfs(i + 1, cur_sign + 1, cur_num + 1); } } else { dfs(i + 1, cur_sign, cur_num + 1); } } } int main() { int cas = 1; while(scanf("%s", str) != EOF) { if(str[0] == '=') break; flag = false; len = strlen(str); printf("Problem %d\n", cas++); if(strcmp(str,"2000=") == 0) { printf(" IMPOSSIBLE\n"); continue; } dfs(0,0,0); if(!flag) printf(" IMPOSSIBLE\n"); } return 0; }

#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           using namespace std; const string sign[] = {"*","+","-",""}; map
          
            Map; set
           
             Set; bool judge(string s) { vector
            
              num, sign; int cur = 0; while(1) { int t = 0; while(isdigit(s[cur])) t = t * 10 + s[cur++] - '0'; num.push_back(t); if(s[cur] == '=') break; sign.push_back(Map[s[cur++]]); } for(int i = 0; i < sign.size(); i++) if(sign[i] == 1) { num[i+1] *= num[i]; sign.erase(sign.begin() + i); num.erase(num.begin() + i); i--; } int t = num[0]; for(int i = 0; i < sign.size(); i++) if(sign[i] == 2) t += num[i + 1]; else t -= num[i + 1]; return t == 2000; } void dfs(string s, int pos, bool f) { if(pos == s.size() - 1) { if(judge(s)) Set.insert(s); return; } for(int i = 0; i < 4; i++) { if(!f && i == 3) continue; string t = s; if(s[pos] != '0') dfs(t.insert(pos,sign[i]), i == 3? pos+1: pos+2, true); else dfs(t.insert(pos,sign[i]), i == 3? pos+1: pos+2, i == 3); } } int main() { int cas = 1; Map['*'] = 1, Map['+'] = 2, Map['-'] = 3; string str; while(cin >> str) { if(str[0] == '=') break; Set.clear(); printf("Problem %d\n", cas++); dfs(str,1,str[0] != '0'); if(!Set.size() || str == "2000=") { printf(" IMPOSSIBLE\n"); continue; } for(set
             
              ::iterator it = Set.begin(); it != Set.end(); it++) cout << " " << *it << endl; } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 2778 AC自动机与矩阵连乘	下一篇：LIghtOJ1038---Race to 1 Again(..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: