设为首页 加入收藏

TOP

UVA - 817 According to Bartjens(二)
2015-07-24 05:35:52 来源: 作者: 【 】 浏览:11
Tags:UVA 817 According Bartjens
符得到结果,字典序输出

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int MAXN = 200; const int INF = 0x3f3f3f3f; typedef long long ll; string str; ll res[MAXN]; int N, M, op[MAXN]; set
        
          f; ll tran(int st, int ed) { if (str[st] == '0' && ed-st > 0) return -1; ll x = 0; for (int i = st; i <= ed; i++) x = x*10 + str[i]-'0'; return x; } void cal() { int m = N-1; int len = str.length()+N-2; string p(len+1, '*'); p[len--] = '='; for (int i = N-1; i >= 0; i--) { ll x = res[i]; if (x == 0) p[len--] = '0'; while (x) { p[len--] = x%10+'0'; x /= 10; } if (i) { if (op[m-1] == 0) { p[len--] = '+'; m--; } else if (op[m-1] == 1) { p[len--] = '-'; m--; } else { p[len--] = '*'; m--; } } } f.insert(p); } void findExpression(int cur, stack
         
           s) { if (cur == N-1) { ll ans = 0; while (!s.empty()) { ans += s.top(); s.pop(); } if (N > 1 && ans == 2000) cal(); return; } for (int i = 0; i < 3; i++) { op[cur] = i; if (i == 0) { s.push(res[cur+1]); findExpression(cur+1, s); s.pop(); } else if (i == 1) { s.push(-res[cur+1]); findExpression(cur+1, s); s.pop(); } else { ll x = res[cur+1]*s.top(); s.pop(); s.push(x); findExpression(cur+1, s); } } } void solve(int cur, int n) { if (cur == str.length()-1) { N = n; stack
          
            s; s.push(res[0]); findExpression(0, s); return; } for (int i = cur; i < str.length()-1; i++) { ll x = tran(cur, i); if (x != -1) { res[n] = x; solve(i+1, n+1); } } } int main() { int cas = 1; while (cin>>str) { f.clear(); if (str.length() == 1 && str[0] == '=') break; printf("Problem %d\n", cas++); solve(0, 0); if (f.size() == 0) printf(" IMPOSSIBLE\n"); else { for (set
           
            ::iterator it = f.begin(); it != f.end(); it++) cout << " " << *it << endl; } } return 0; }
           
          
         
        
       
      
     
    
   
  



首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇C++ 虚函数的缺省参数问题 下一篇POJ-2201-Cartesian Tree(笛卡尔..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: