uva10400

제목 대의: 연산 기호는 우선순위가 없고 제시된 숫자는 순서대로 +-*/를 이용하여 결과를 얻어내고 결과가 나오지 않으면 출력이 풀리지 않는다.
생각: 직접 dfs
코드:

#include <iostream>
using namespace std;
#include <stdio.h>
#include <cstring>
#include <cmath>

int p[105],flag,vis[105][64001],num,target,o[105];

void solve(int sum,int d) {

    int i,s;
    if(d > num-1 && sum == target) flag = 1;
    if(flag || d >num-1 || abs(sum) >32000) return ;
    for(i = 1; i<= 4; i++) {
        o[d - 1] = i;
        s = 32001;
        if(i == 1) s = sum + p[d];
        if(i == 2) s = sum - p[d];
        if(i == 3) s = sum * p[d];
        if(i == 4 && (sum %p[d] == 0) && p[d]!= 0) s = sum/p[d];
        if(abs(s) <= 32000 && vis[d - 1][s] == 0) {
            vis[d - 1][s] = 1;
            solve(s,d+1);
        }
        if(flag) return ;
    }
}

int main() {

    int cases;
    scanf("%d",&cases);
    while(cases--) {
        scanf("%d",&num);
        for(int i = 0 ; i < num; i++)
            scanf("%d",&p[i]);
        scanf("%d",&target);
    // cout << 1<<endl;
        flag = 0;
        memset(vis,0,sizeof(vis));
        solve(p[0],1);
// cout << 1;
        if(flag) {
            for(int i = 0; i < num-1 ; i++) {
                printf("%d",p[i]);
                if(o[i] == 1) printf("+");
                if(o[i] == 2) printf("-");
                if(o[i] == 3) printf("*");
                if(o[i] == 4) printf("/");
            }
            printf("%d=%d
",p[num - 1],target);
        }
        else
            printf("NO EXPRESSION
");
    }
    return 0;
}