問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1775思路:
簡(jiǎn)單題，可以打表，可以DFS，還可以動(dòng)規(guī)
代碼(dfs):
1 /* Note: 10! = 3628800 */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_LEN 10
6 int facs[MAX_LEN];
7 int mark, n;
8
9 void
10 init()
11 {
12 int i, f = 1;
13 facs[0] = 1;
14 for(i=1; i<MAX_LEN; i++) {
15 facs[i] = f*i;
16 f = facs[i];
17 }
18 }
19
20 void
21 dfs(int depth, int sum)
22 {
23 if(sum == n) {
24 mark = 1;
25 return;
26 }
27 if(depth>=MAX_LEN || mark)
28 return;
29 dfs(depth+1, sum+facs[depth]);
30 dfs(depth+1, sum);
31 }
32
33 int
34 main(int argc, char **argv)
35 {
36 init();
37 while(scanf("%d", &n)!=EOF && n>=0) {
38 mark = 0;
39 if(n > 0)
40 dfs(0, 0);
41 printf("%s\n", mark?"YES":"NO");
42 }
43 }
代碼(table, from
http://blog.chinaunix.net/u3/105033/showart_2199237.html):
1 #include<iostream>
2 using namespace std;
3 bool b[1000001];
4 int sum=0;
5 int a[10]={1,1,2,6,24,120,720,5040,40320,362880};
6 void calculate(int n)
7 {
8 if(n>=10)
9 return ;
10 sum+=a[n];
11 b[sum]=true;
12 calculate(n+1);
13 sum-=a[n];
14 calculate(n+1);
15 }
16 int main()
17 {
18 memset(b,0,sizeof(b[0]));
19 calculate(0);
20 b[0]=false;
21 int n;
22 cin>>n;
23 while( n>=0)
24 {
25 if(b[n])
26 cout<<"YES"<<endl;
27 else
28 cout<<"NO"<<endl;
29 cin>>n;
30 }
31 return 0;
32 }