UESTC 2016 Summer Training #1 Div.2 L – Plus or Minus (A) dfs

Source

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=121539#problem/L

My Solution

dfs就好， 好久没用写dfs了，简单dfs还是Debug了好长时间， 尴尬⊙﹏⊙‖∣

记得把那些转移的东西写在参数里

读入char类型， 记得看看要不要用getchar吸掉换行空格什么的

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 28;
int val[maxn];
char plusmi[maxn];
int ans, n;
void dfs(int k, int sum, int q)
{
    if(k == n){
        if(sum == 0) ans = min(ans, q);
        return;
    }

    for(int i = 0; i < 2; i++){
        if(i == 0){
            if(plusmi[k] == '-') dfs(k+1, sum + val[k], q + 1);
            else dfs(k+1, sum + val[k], q);
        }
        else{
            if(plusmi[k] == '+') dfs(k+1, sum - val[k], q + 1);
            else dfs(k+1, sum - val[k], q);
        }
    }
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    int T = 2;
    while(T--){
    #endif // LOCAL
    scanf("%d", &n);
    scanf("%d", &val[0]);
    for(int i = 1; i < n; i++){

        getchar();
        scanf("%c", &plusmi[i]);
        scanf("%d", &val[i]);


    }
    /*
    printf("%d", val[0]);
    for(int i = 1; i < n; i++)
        printf("%c%d",plusmi[i] , val[i]);
    */
    ans = 1000;
    dfs(1,val[0], 0);

    if(ans != 1000) printf("%d", ans);
    else printf("-1");

    #ifdef LOCAL
    printf("n");
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx