USACO 2.33 Zero Sum

题意：

考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。现在请在数列中插入“+”表示加，或者“-”表示减，“ ”表示空白(例如1-2 3就等于1-23)，来将每一对数字组合在一起（请不要在第一个数字前插入符号）。计算该表达式的结果并判断其值是否为0。请你写一个程序找出所有产生和为零的长度为N的数列。

分析：DFS枚举就好了

关键就是 处理‘ ’，用last保存最近的一个连续的整数，不将该数进行运算，sum表示last之前的运算结果

若当前选择了 ' '：sum=sum-last+last*10+s+1(last>0)；sum=sum-last+last*10-s-1(last<0)； 
                  last=last*10+s+1(last>0)；last=last*10-s-1(last<0)
若当前选择了 '+'：sum=sum+s+1；last=s+1
若当前选择了 '-'：sum=sum-s-1；last=-s-1

/*
ID: nanke691
LANG: C++
TASK: zerosum
*/
#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;
char str[18];
int n;
void DFS(int k, int sum, int last)
{
	if (k == n)
	{
		if (sum+last == 0) cout<<str<<endl;
		return;
	}
	str[k*2-1] = ' ';
	DFS(k+1, sum, last > 0 ? last*10+k+1 : last*10-k-1);
	str[k*2-1] = '+';
	DFS(k+1, sum+last, k+1);
	str[k*2-1] = '-';
	DFS(k+1, sum+last, -k-1);
}
 
int main()
{
	freopen("zerosum.in", "r", stdin);
	freopen("zerosum.out", "w", stdout);
	cin>>n;
	for (int i = 0; i < n; ++i)
		str[i*2] = i+'1';
	DFS(1, 0, 1);
}