USACO-2.3Zero Sum

一个简单dfs，只是填充符号后的求和写的有点复杂了。

/*
ID:15674811
LANG:C++
PROG:zerosum
*/

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<fstream>
using namespace std;

int n,tmp[12];
char str[20];

ofstream fout("zerosum.out");
ifstream fin("zerosum.in");

int check()
{
    char str1[20];
    int cnt=1;
    tmp[cnt]=1;
    for(int i=2;i<=n;i++)
        if(str[i]==' ')
            tmp[cnt]=tmp[cnt]*10+i;
        else
            tmp[++cnt]=i;
    int k=2;
    for(int i=2;i<=n;i++)
        if(str[i]!=' ')
           str1[k++]=str[i];
    int sum=tmp[1];
    for(int i=2;i<k;i++)
        if(str1[i]=='+')
            sum+=tmp[i];
        else
            sum-=tmp[i];
    if(sum==0)
    {
        fout<<1;
        for(int i=2;i<=n;i++)
            fout<<str[i]<<i;
        fout<<endl;
    }
}

void dfs(int cur)
{
    if(cur==n+1)
    {
        check();
        return ;
    }
    str[cur]=' ';
    dfs(cur+1);
    str[cur]='+';
    dfs(cur+1);
    str[cur]='-';
    dfs(cur+1);
}

int main()
{
    while(fin>>n)
    {
        dfs(2);
    }
  return 0;
}