poj1579 Function Run Fun

Function Run Fun

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions:13896		Accepted: 7233

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

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 <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 int ww[22][22][22];
 5 int w(int a, int b, int c){
 6   if (a <= 0 || b <= 0 || c <= 0) return 1;
 7   if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
 8   if (ww[a][b][c] > 0) return ww[a][b][c];
 9   if (a < b && b < c) return ww[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
10   else return ww[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1);
11 }
12 int main(void){
13   int a, b, c;
14 #ifndef ONLINE_JUDGE
15   freopen("poj1759.in", "r", stdin);
16 #endif
17   while (~scanf("%d%d%d", &a, &b, &c)){
18     if (a == b && b == c && c == -1) break;
19     memset(ww, -1, sizeof(ww));
20     printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c));
21   }
22   return 0;
23 }

基本思想就是标记的思想，避免重复计算，水题，看了讨论板学会的，突然发现好久不做水题了……

有一个事情，就是敲代码的时候，要认真，千万要避免打字错误……次奥，超级让人崩溃的