POJ 1579(メモアルゴリズム)

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
",a,b,c,ans);//   4   ，                  PE 

67     }

68     return 0;

69 }

70  

71