USACO 零的数列 Zero Sum

这道题还是搜索，将每个符号待人，3^9次方的时间还是可以接受的。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int s[22]={1,2,3,4,5,6,7,8,9},sign[22]={1};//数字和其前方符号,一一对应
int n;
int sum(void){                                          //求和 
	int sum=0,i,now,index;
	now=0,index=1;
	for(i=n-1;i>=0;i--){
		now+=s[i]*index;
		if(sign[i]==0){
			index*=10;
			continue; 
		}
		else{
			sum+=now*sign[i];
			now=0,index=1;
		}
	}
	return sum;
}
void dfs(int p){         //下标为p的已经决定	
	int i;
	if(p==n-1){
		if(sum()==0){
			printf("%d",s[0]);
			for(i=1;i<n;i++){
				if(sign[i]==1) printf("+");
				else if(sign[i]==-1) printf("-");
				else printf(" ");
				printf("%d",s[i]);
			}
			printf("
");
		}
		return;
	}
	//注意:ascii码中' '<'+'<'-'
	sign[p+1]=0,dfs(p+1);
	sign[p+1]=1,dfs(p+1);
	sign[p+1]=-1,dfs(p+1);
}
int main(){
	scanf("%d",&n);
	dfs(0);
	return 0;
}