【题目来源】
洛谷：P1464 Function - 洛谷 (luogu.com.cn)
【题目描述】
对于一个递归函数 \(w(a,b,c)\)
- 如果 \(a\le 0\) 或 \(b\le 0\) 或 \(c\le 0\) 就返回值 \(1\)。
- 如果 \(a\gt 20\) 或 \(b\gt 20\) 或 \(c\gt 20\) 就返回 \(w(20,20,20)\)
- 如果 \(a\lt b\) 并且 \(b\lt c\) 就返回 \(w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,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\) 均为 \(15\) 时，调用的次数将非常的多。你要想个办法才行。
注意：例如 \(w(30,-1,0)\) 又满足条件 \(1\) 又满足条件 \(2\)，请按照最上面的条件来算，答案为 \(1\)。
【输入】
会有若干行。
并以 \(−1,−1,−1\) 结束。
【输出】
输出若干行，每一行格式：
w(a, b, c) = ans
注意空格。
【输入样例】
1 1 1
2 2 2
-1 -1 -1
【输出样例】
w(1, 1, 1) = 2
w(2, 2, 2) = 4
【解题思路】
【算法标签】
《洛谷 P1464 Function》 #搜索# #递归# #记忆化搜索#
【代码详解】
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
LL a, b, c;
int w1[25][25][25]; // 记忆化数组，存储已计算结果// 递归计算w(a,b,c)函数
int w(LL a, LL b, LL c)
{// 边界条件1：任一参数≤0时返回1if (a <= 0 || b <= 0 || c <= 0) return 1;// 边界条件2：任一参数>20时按20计算if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);// 记忆化：如果已计算过，直接返回结果if (w1[a][b][c] != 0) return w1[a][b][c];// 递归情况1：a<b且b<cif (a < b && b < c) w1[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);// 递归情况2：其他情况else w1[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);return w1[a][b][c];
}int main()
{// 初始化记忆化数组为0memset(w1, 0, sizeof(w1));while (true) {cin >> a >> b >> c;// 输入终止条件if (a == -1 && b == -1 && c == -1) break;// 计算并格式化输出结果printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));}return 0;
}
【运行结果】
1 1 1
w(1, 1, 1) = 2
2 2 2
w(2, 2, 2) = 4
-1 -1 -1