A - Function Run Fun

A - Function Run Fun A - Function Run Fun 

 A - Function Run Fun

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

Sponsor

没啥说的 

在递归中打表： 

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
typedef long long ll;
ll e, r, t;
ll p[21][21][21];
ll w(ll a, ll b, ll c) {
	if (p[a][b][c]) return p[a][b][c];
	if (a <= 0 || b <= 0 || c <= 0) {
		p[a][b][c] += 1;//在递归中打表，不用专门写打表函数了
		return 1;
	}
	else if (a > 20 || b > 20 || c > 20) {
		int k = w(20, 20, 20);
		p[a][b][c] += k;
		return k;
	}
	else if (a < b && b < c) {
		int k = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
		p[a][b][c] += k;
		return k;
	}
	else {
		int 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);
		p[a][b][c] += k;
		return k;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	while (scanf("%lld%lld%lld", &e, &r, &t), e != -1, r != -1, t != -1) {
		ll lowe = e, lowr = r, lowt = t;
		if (e <= 0 || r <= 0 || t <= 0) lowe = 0, lowr = 0, lowt = 0;//条件<=0优先于条件>=20，这一行要在下一行前面
		else if (e > 20 || r > 20 || t > 20) lowe = 20, lowr = 20, lowt = 20;
		
		printf("w(%lld, %lld, %lld) = %lldn", e, r, t, w(lowe, lowr, lowt));
	}
}

在递归外打表： 

下面这个方法我把递归和打表分开了，比较清晰好懂

#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
typedef long long ll;
ll e, r, t;
ll p[21][21][21];
ll w(ll a, ll b, ll c) {//递归
	if (p[a][b][c]) return p[a][b][c];
	if (a <= 0 || b <= 0 || c <= 0) {
		p[a][b][c] = 1;
		return 1;
	}
	else if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
	else if (a < b && b < c) return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
	else return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
void menu() {//打表
	for (int i = 0; i <= 20; i++) {
		for (int j = 0; j <= 20; j++) {
			for (int k = 0; k <= 20; k++) {
				p[i][j][k] = w(i, j, k);
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	menu();
	while (scanf("%lld%lld%lld", &e, &r, &t), e != -1, r != -1, t != -1) {
		ll lowe = e, lowr = r, lowt = t;
		if (e <= 0 || r <= 0 || t <= 0) lowe = 0, lowr = 0, lowt = 0;//条件<=0优先于条件>=20，这一行要在下一行前面
		else if (e > 20 || r > 20 || t > 20) lowe = 20, lowr = 20, lowt = 20;
		printf("w(%lld, %lld, %lld) = %lldn", e, r, t, p[lowe][lowr][lowt]);
	}
}