POJ1579:Function Run Fun

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

Source

Pacific Northwest 1999

方法一：

直接递归会超时，预处理即可。实现把所有结果存到三维数组中。

 #include <iostream>

 #include <cstdio>

 using namespace std;

 int main()

 {

     int w[][][], ans, a, b, c;

     //预处理

     for(int i = ; i < ; i++)

         for(int j = ; j < ; j++)

             for(int k = ; k < ; k++)

             {

                 if(!i || !j || !k) w[i][j][k] = ;

                 else if(i < j && j < k)

                     w[i][j][k] = w[i][j][k-] + w[i][j-][k-] - w[i][j-][k];

                     //w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

                 else

                     w[i][j][k] = w[i-][j][k] + w[i-][j-][k] + w[i-][j][k-] - w[i-][j-][k-];

                     //w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

             }

     while(scanf("%d %d %d", &a, &b, &c))

     {

         if(a == - && b == - && c == -) break;

         if(a <=  || b <=  || c <= ) ans = ;

         else if(a >  || b >  || c > ) ans = w[][][];

         else ans = w[a][b][c];

         printf("w(%d, %d, %d) = %d\n", a, b, c, ans);

     }

     return ;

 }

方法二：

总之要先把之前运算出来的结果存到三维数组中，避免重复运算。

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 using namespace std;

 int dp[][][];

 int dfs(int a,int b,int c)

 {

     if(a<= || b<= || c<=)

         return ;

     if(a> || b> || c>)

         return dfs(,,);

     if(dp[a][b][c])

         return dp[a][b][c];

     if(a<b && b<c)

         dp[a][b][c] = dfs(a,b,c-)+dfs(a,b-,c-)-dfs(a,b-,c);

     else

         dp[a][b][c] = dfs(a-,b,c)+dfs(a-,b-,c)+dfs(a-,b,c-)-dfs(a-,b-,c-);

     return dp[a][b][c];

 }

 int main()

 {

     int a,b,c;

     memset(dp,,sizeof(dp));

     while(~scanf("%d%d%d",&a,&b,&c))

     {

         if(a == - && b == - && c == -)

             break;

         printf("w(%d, %d, %d) = %d\n",a,b,c,dfs(a,b,c));

     }

     return ;

 }

巴特西

POJ1579:Function Run Fun

最新文章

热门文章