Function Run Fun
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 13491 | Accepted: 7023 |
Description
We all love recursion! Don't we?
Consider a three-parameter recursive function w(a, b, c):
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15, b = 15, c = 15), the program takes hours to run because of the massive recursion.
Input
The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print the result.
Output
Print the value for w(a,b,c) for each triple.
Sample Input
1 1 1 2 2 2 10 4 6 50 50 50 -1 7 18 -1 -1 -1
Sample Output
w(1, 1, 1) = 2 w(2, 2, 2) = 4 w(10, 4, 6) = 523 w(50, 50, 50) = 1048576 w(-1, 7, 18) = 1
1 #include <iostream>
2 #include <cstring>
3 #include <cstdio>
4 using namespace std;
5
6 const int N = 100;
7 int d[N][N][N];
8 bool vis[N][N][N];
9
10 //a,b,c可能是负值，而数组下标无负值，需特殊处理
11 int fun(int a,int b,int c)//必须带参数，因为中间需要转存且参数变了
12 {
13 // if(((a<=0||b<=0||c<=0)||(a>20||b>20||c>20)||(a<b&&b<c))&&!vis[a][b][c])//这个条件不对因为若abc其一为负数便执行了else if，需要把第一个条件单独搞出来
14 if((a<=0||b<=0||c<=0)||(((a>20||b>20||c>20)||(a<b&&b<c))&&!vis[a][b][c]))
15 {
16 if(a<=0||b<=0||c<=0)
17 return 1;
18 if(a>20||b>20||c>20&&!vis[a][b][c])
19 {
20 d[a][b][c] = fun(20,20,20);
21 //d[20][20][20] = fun(20,20,20);
22 d[20][20][20] = d[a][b][c];
23 vis[a][b][c] = 1;
24 vis[20][20][20] = 1;
25 }
26 if(a<b&&b<c&&!vis[a][b][c])
27 {
28 d[a][b][c-1] = fun(a,b,c-1);
29 vis[a][b][c-1] = 1;
30 d[a][b-1][c-1] = fun(a,b-1,c-1);
31 vis[a][b-1][c-1] = 1;
32 d[a][b-1][c] = fun(a,b-1,c);
33 vis[a][b-1][c] = 1;
34 d[a][b][c] =d[a][b][c-1] + d[a][b-1][c-1] - d[a][b-1][c];
35 vis[a][b][c] = 1;
36 }
37 }
38 else if(!vis[a][b][c])//加上了if后效率大增
39 {
40 d[a-1][b][c] = fun(a-1, b, c);
41 vis[a-1][b][c] = 1;
42 d[a-1][b-1][c] = fun(a-1, b-1, c);
43 vis[a-1][b-1][c] = 1;
44 d[a-1][b][c-1] = fun(a-1, b, c-1);
45 vis[a-1][b][c-1] = 1;
46 d[a-1][b-1][c-1] = fun(a-1, b-1, c-1);
47 vis[a-1][b-1][c-1] = 1;
48 d[a][b][c] = d[a-1][b][c] + d[a-1][b-1][c] + d[a-1][b][c-1] - d[a-1][b-1][c-1];
49 vis[a][b][c] = 1;
50 }
51 return d[a][b][c];
52 }
53
54 int main()
55 {
56 int i,j,k;
57 int a, b, c;
58 while(cin>>a>>b>>c&&!(a==-1&&b==-1&&c==-1))
59 {
60 memset(d,-1,sizeof(d));
61 memset(vis,0,sizeof(vis));
62 vis[0][0][0] = 1;
63 d[0][0][0] = 1;
64 int ans = fun(a,b,c);
65 //cout<<"w("<<a<<","<<b","<<c<<") = "<<ans<<endl;
66 printf("w(%d, %d, %d) = %d\n",a,b,c,ans);//注意有4个空格，原来只注意到了等号两侧的空格吃了一个PE
67 }
68 return 0;
69 }
70
71