[PacNW 1999] Function(Recursive Function w) 题解

思路分析

有效递归状态仅有 $1 \le a, b, c \le 20$ 共 $20^3 = 8000$ 种，用三维数组 memo[21][21][21] 做记忆化搜索即可。注意三点细节：

1. 输入的 $a, b, c$ 可达 $64$ 位有符号整数极值，必须用 long long 读入并原样输出；
2. 结束条件是 a == -1 && b == -1 && c == -1（仅某一个为 -1 时不能提前退出！）；
3. 必须先判断 a <= 0 || b <= 0 || c <= 0 返回 1，再判断 a > 20 || b > 20 || c > 20 转为 w(20, 20, 20)。

参考代码

#include <iostream>
using namespace std;

long long memoArr[22][22][22];
bool visArr[22][22][22];

long long w(long long a, long long b, long long c)
{
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
    if (visArr[a][b][c]) return memoArr[a][b][c];
    visArr[a][b][c] = true;
    if (a < b && b < c)
        memoArr[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    else
        memoArr[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 memoArr[a][b][c];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long a, b, c;
    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;
}