uva 10317

暴力剪枝就對了

 

一開始dfs弄錯了吃了WA，剪枝沒剪好TLE

最後終於AC了

/*
 * GCA : "Computer is artificial subject absolutely,Math is God"
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) __typeof(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(__VA_ARGS__)
#else
#define VAR(a,b) __typeof(b) a=(b)
#define debug(...)
#endif
typedef unsigned int uint;
typedef long long int Int;
typedef unsigned long long int UInt;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\n")
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define M 20
#define PB push_back
#define oo INT_MAX
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-9
#define X first
#define Y second
inline bool xdy(double x,double y){return x>y+eps;}
inline bool xddy(double x,double y){return x>y-eps;}
inline bool xcy(double x,double y){return x<y-eps;}
inline bool xcdy(double x,double y){return x<y+eps;}
const Int mod=1000000007;
int n;
char str[100005];
int lnum,rnum;
int lef[20],righ[20];
int have[20];
int hnum;
int vis[20];
int oper[100];
int opel[100];
int all;
bool ok=false;
bool dfs(int dep,int index,int now){
    if(dep==lnum){
        if(now==all/2){
            int t=0;
            for(int i=0;i<hnum;i++){
                if(!vis[i])righ[t++]=have[i];
            }
            return true;
        }
    }
    for(int i=index;i<hnum;i++){
        vis[i]=1;
        lef[dep]=have[i];
        if(now+lef[dep]>all/2){
            vis[i]=0;
            continue;
        }
        if(dfs(dep+1,i+1,now+lef[dep]))return true;
        vis[i]=0;
    }
    return false;

}

int main() {
    ios_base::sync_with_stdio(0);
    while(gets(str)){
        Set(vis,0);
        int len=strlen(str);
        ok=hnum=lnum=rnum=all=0;
        int reall=0,realr=0;
        bool turn=false;
        int dir=0;
        for(int k,j=0;j<len;j+=k){
            char tmp[1005];
            sscanf(str+j,"%s%n",tmp,&k);
            if(isdigit(tmp[0])){
                int t;
                sscanf(tmp,"%d",&have[hnum++]);
                all+=have[hnum-1];
                if(!dir){
                    if(!turn){
                        lnum++;
                        opel[reall++]=0;
                    }
                    else{
                        rnum++;
                        opel[reall++]=1;
                    }
                }else{
                    if(!turn){
                        rnum++;
                        oper[realr++]=0;
                    }
                    else{
                        lnum++;
                        oper[realr++]=1;
                    }
                }
            }else{
                if(tmp[0]=='-')turn=1;
                else if(tmp[0]=='+')turn=0;
                else if(tmp[0]=='='){
                    dir=1;
                    turn=0;
                }
            }
//            debug("%d %d %d %d %d %d\n",lnum,rnum,hnum,reall,realr,all);
        }
        if(!(all&1)&&dfs(0,0,0)){
//            for(int i=0;i<lnum;i++)printf("%d ",lef[i]);
//            Pln();
//            for(int i=0;i<rnum;i++)printf("%d ",righ[i]);
//            Pln();
            int nowr=0,nowl=0;
            printf("%d",lef[nowl++]);
            for(int i=1;i<reall;i++){
                if(!opel[i]){
                    printf(" + %d",lef[nowl++]);
                }else{
                    printf(" - %d",righ[nowr++]);
                }
            }
            printf(" = %d",righ[nowr++]);
            for(int i=1;i<realr;i++){
                if(!oper[i]){
                    printf(" + %d",righ[nowr++]);
                }else{
                    printf(" - %d",lef[nowl++]);
                }
            }Pln();
        }else puts("no solution");


    }

















}