POJ 1775 Sum of Factorials C++版

发表于 更新于

题目链接：http://poj.org/problem?id=1775

不难，解释下题意 判断一个数是否能写为多个阶乘的和

先打表，计算出0-9的阶乘，然后深搜每一个数的组合，其中回溯的方式表示成了||这样搜索不算效率，也能AC！

不过有一点，我没注意，就是0的情况，害我WA了半天，加上个排除就好了！

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*Problem: 1775		User: awq123
**Memory: 216K		Time: 500MS
**Language: C++		Result: Accepted
*/
#include <IOSTREAM>
using namespace std;

int num[10]={1,1,2,6,24,120,720,5040,40320,362880};

int dfs(int n,int i)
{
	if(n==0)
		return 1;
	if(n<0)
		return 0;
	if(i>9)
		return 0;
	return dfs(n-num[i],i+1)||dfs(n,i+1);
}

int main()
{
	int n;
	while(cin>>n&&n;>=0)
	{
		if(n==0)
			cout<<"NO"<<endl;
		else if(dfs(n,0))
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}

}