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.
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