[DFS]Acdream 1431

题意

      输入n(n<=500),求有多少种n个数字的组合使得n个数字的和等于n个数字的乘积

思路

      dfs即可，注意剪枝

 

/*************************************************************************
    > File Name: main.cpp
    > Author: bbezxcy
    > Mail:[e-mail] 
    > Created Time: 2014年10月16日 星期四 18时40分16秒
 ************************************************************************/

#include <iostream>
#include <cstdio>
using namespace std;
int n;
int res;
void dfs(int num,int val,int val1,int dep){
	if(dep>n)return;	
	int i;
	for(i=num;i<=n;i++){
		int a=i*val;
		int b=i+val1;
		if(a==b+n-dep){
			res++;
			return;
		}else{
			if(a<b+n-dep)
			dfs(i,a,b,dep+1);
		}
	}
}
int main(){
	while(scanf("%d",&n)!=EOF){
		if(!n)break;
		if(n==1){
			printf("1\n");
			continue;
		}
		res=0;
		dfs(2,1,0,1);
		printf("%d\n",res);
	}
	return 0;
}