洛谷题单指南-递推与递归-P1464 Function

原题链接：https://www.luogu.com.cn/problem/P1464

题意解读：虽然a、b、c可输入的范围比较大，但是递归中，只会限制在0-20以内，由于递归中有大量的重复计算，因此需要采用记忆化搜索来保存已经计算过的递归函数值。

解题思路：

定义三位数组LL mem[25][25][25]，mem[a][b][c]保存w(a, b, c)的值，递归中判断a、b、c是否已经计算过，如果计算过直接返回结果

需要注意初次调用w(a,b,c)时a、b、c的范围可能很大，不能在函数一开始就进行mem[a][b][c]的判断和返回，要在前两个条件结束之后，

这样可以保证a、b、c范围限定在0-20以内，不会导致数组越界。

100分代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
LL a, b, c;

LL mem[25][25][25];

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

int main()
{
    while(cin >> a >> b >> c && (a != -1 || b != -1 || c != -1))
    {
        printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a, b, c));
    }
    return 0;
}