问题 2199 --记忆化搜索 - 递归函数的乐趣

2199: 记忆化搜索 - 递归函数的乐趣

时间限制: 1 Sec  内存限制: 128 MB
提交: 363  解决: 192
[提交][状态][命题人:]

题目描述

我们都喜欢递归! 不是吗?
考虑一个有三个参数的递归函数w(a, b, c):
如果a <= 0或b <= 0或c <= 0,则
w(a, b, c)=1。
如果a> 20或b> 20或c> 20,则
w(a, b, c)=w(20, 20, 20)。
如果a <b且b <c,则
w(a, b, c)=w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
否则它返回:
w(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)
这是一个易于实现的功能。 问题是,如果直接实现,对于a,b和c的中等值(例如,a = 15,b = 15,c = 15),由于大量递归,程序需要数小时才能运行。

输入

程序的输入将是一系列整数三元组,每行一个,分别代表a,b,c。直到文件结束标志为-1 -1 -1。

输出

对于每组数据,输出w(a,b,c)。
样例输入
Copy
1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1
样例输出
Copy
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

提示

来源

[提交][状态]