Function Run Fun

Time Limit: 2000/1000 MS ( Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2376 Accepted Submission(s): 1187

Problem 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

题意：修改给你的这个递归，使他能够处理更大的数据

解析，a,b,c被控制在1~20之间，所以用记忆化搜索的方式记忆那些数据防止重复就行了

#include 
   
     #include 
    
      #include 
     
       using namespace std; int dp[22][22][22],s=0; //记录防止重复搜索 int w(int a,int b,int c) { if(a<=0||b<=0||c<=0)return 1; if(a>20||b>20||c>20)return w(20,20,20); if(dp[a][b][c])return dp[a][b][c]; //使用记忆点防止重复 if(a

莫名其妙，就直接把记忆化的思想加进来就搞定了，当年真是白活了啊！！

HDU--1331--Function Run Fun--记忆化搜索

Function Run Fun