P1464 [PacNW 1999] Function
题目描述
对于一个递归函数 \(w(a,b,c)\)
- 如果 \(a \le 0\) 或 \(b \le 0\) 或 \(c \le 0\) 就返回值 \(1\)。
- 如果 \(a>20\) 或 \(b>20\) 或 \(c>20\) 就返回 \(w(20,20,20)\)
- 如果 \(a<b\) 并且 \(b<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
说明/提示
数据规模与约定
保证输入的数在 \([-9223372036854775808,9223372036854775807]\) 之间，并且是整数。
保证不包括 \(-1, -1, -1\) 的输入行数 \(T\) 满足 \(1 \leq T \leq 10 ^ 5\)。
Tip
📌 题目分析
给定条件：
通过多次递归调用求函数值。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么需要记忆化搜索
纯粹的递归是树形结构的展开。
当计算 w(15, 15, 15) 时，函数会分裂出无数个分支，存在海量的重复计算，导致时间复杂度呈指数级爆炸（超时 TLE）。
我们必须开辟一个数组，把算过的结果存起来。下次再遇到相同的参数时，直接查表返回即可。
2️⃣ 记忆化数组开多大
虽然题目给定的数据范围达到了 long long 极限，但仔细观察第二条规则：
这意味着任何大于 20 的参数最终都会变成 20。而小于等于 0 的参数会直接返回 1。
所以真正会进入递归并且需要记录的参数范围只有 [1, 20]。
开一个 dp[25][25][25] 的三维数组绰绰有余。
3️⃣ 判断条件的绝对顺序
题目中有特别的提示：w(30, -1, 0) 满足多条规则时，必须按最上面的条件算。
也就是说，代码里的 if 判断顺序决不能打乱：
1. 先判 <= 0
2. 再判 > 20
3. 最后再查 dp 数组和进入后续的递归分支
4️⃣ 时间复杂度
由于参数范围被压缩到了 20 以内，每个状态最多只会被计算一次：
这对于计算机来说几乎是一瞬间的事情，极快。
💻 C++代码
#include <iostream>
using namespace std;
// 全局数组默认初始化为 0，刚好可以用来判断是否已经计算过
long long dp[25][25][25];
long long w(long long a, long long b, long long c) {
// 1. 严格按照题目给定的顺序进行特判
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
// 2. 如果已经计算过，直接返回记忆数组里的值
if (dp[a][b][c] != 0) return dp[a][b][c];
// 3. 未计算过，则按规则递归计算，并存入 dp 数组
if (a < b && b < c) {
dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
} else {
dp[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 dp[a][b][c];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b, c;
// 不断读取，直到输入为 -1 -1 -1 结束
while (cin >> a >> b >> c) {
if (a == -1 && b == -1 && c == -1) break;
// 注意输出格式，逗号后面有空格
cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
}
return 0;
}
⚠️ 易错点
❌ 1. 数组越界导致段错误 (RE)
如果不先判断 a <= 0 和 a > 20，直接写 if (dp[a][b][c] != 0)，当传入负数或者极大的数字时，会直接访问数组非法内存导致崩溃。查表必须放在边界检查之后。
❌ 2. 忽略数据范围
虽然需要记录的状态只在 20 以内，但输入的参数非常大。
函数参数和输入变量必须使用 long long 接收，否则会导致整数溢出。
❌ 3. 输出格式的空格踩坑
洛谷的字符串匹配极其严格：
如果写成 w(a,b,c)=ans，哪怕结果全对，也会爆零 (WA)。
🚀 一句话总结
🔥 补充
动态规划 (DP) 与 记忆化搜索：
这题其实就是 DP。只是 DP 通常用 for 循环从底向上推导（自底向上），而记忆化搜索是用递归函数结合数组来求值（自顶向下）。
对于这种有着复杂的分支跳跃条件（如某些特定状态不需要算）的函数，记忆化搜索写起来比用 for 循环硬推 DP 要优雅且简单得多。