[ACM_POJ_1579]动态规划入门练习（二）Function Run Fun

杰拉斯 | 时间：2012-04-03, Tue | 22,524 views
编程算法　

Function Run Fun

Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 12362 Accepted: 6466

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

POJ1579

题目一开始就说了We all love recursion! Don't we?（我们都喜欢递归！不是吗？）但从这道题目的复杂度来看，用递归来解决的话必然TLE，因此还是类似斐波那契数列的思路，用空间换时间。

代码如下：

#include<stdio.h>
int w[21][21][21] = {1};
int getw(int a, int b, int c){
	if(a <= 0 || b <= 0 || c <= 0)
		return 1;
	else if(a > 20 || b > 20 || c > 20)
		return w[20][20][20];
	else
		return w[a][b][c];
	return 1;
}
int main(){
	int a, b, c;
	for(a = 1; a <= 20; ++a){
		for(b = 1; b <= 20; ++b){
			for(c = 1; c <= 20; ++c){
				if(a < b && b < c){
					w[a][b][c] = getw(a, b, c-1) + getw(a, b-1, c-1) - getw(a, b-1, c);
				}else{
					w[a][b][c] = getw(a-1, b, c) + getw(a-1, b-1, c) + getw(a-1, b, c-1) - getw(a-1, b-1, c-1);
				}
			}
		}
	}
	while(scanf("%d%d%d", &a, &b, &c) && (a + 1) || (b + 1) || (c + 1))
		printf("w(%d, %d, %d) = %d\n", a, b, c, getw(a, b, c));
	return 0;
}

话说这是我在北京大学ACM上做的第二道题，第一道题是：动态规划入门（一）The Triangle，两道题都是一次通过，让我对北京大学在线评测系统的印象分顿时提高不少 [偷笑] 。。

如需转载请注明出处：杰拉斯的博客

杰拉斯的博客