P1464与递归函数的记忆化搜索

原题地址：https://www.luogu.com.cn/problem/P1464

1. 如果 $a≤0$ 或 $b≤0$ 或 $c≤0$ 就返回值 1

2. 如果 $a>20$ 或 $b>20$ 或 $c>20$ 就返回 w(20,20,20)$

3. 如果 $a<b$ 并且 $b<c$ 就返回 $w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)$

4. else $w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)$

注意：例如 $w(30,−1,0)$ 又满足条件 1 又满足条件 2，请按照最上面的条件来算，答案为 1。

分析：本题考察递归的记忆化漏洞，记忆化不仅是递归的动态规划，更是对递归的优化，并非从底自上的动态规划填表法

其他注意事项

• 保证输入的数在 $[−9223372036854775808,9223372036854775807]$ 之间，并且是整数。

• 保证不包括 $−1,−1,−1$ 的输入行数 $T$ 满足 $1≤T≤10^5$

综上所述还需要开longlong防止爆掉

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;

ll memo[21][21][21];
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 w(20,20,20);
    if (memo[a][b][c] != -1) {
        return memo[a][b][c];
    }
    if (a<b && b<c) {
        memo[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c);
    } else {
        memo[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 memo[a][b][c];
}

int main() {
    memset(memo, -1, sizeof(memo));
    ll a,b,c;
    while(cin>>a>>b>>c) {
        if(a==-1 && b==-1 &&c==-1) break;
        ll ans = w(a,b,c);
        cout << "w(" << a << ", " << b << ", " << c << ") = " << ans << endl;
    }
    return 0;
}

以下的QFA来自暂时can not fly的fish在做题中犯的一些错误

Q: if(a==-1 && b==-1 &&c==-1) break; 为什么这一步是break掉而不是return 一个值？

A: 因为这行代码的作用是满足判断条件后就跳出输入循环

Q: 意思就是仅跳过这个long long result = w(a, b, c); 调用w函数的代码然后return 0;是吗？

A: Yes~

Q: 在上述代码中把w函数写在了main函数前面，代码是先经过主函数的读取数字再调用了w函数进行计算，那按照这个处理逻辑能否把main函数写在w函数前面?

A: 在C++中，函数顺序定义会影响其可见性，以我们的代码为例，我们把main函数写在w函数前，但是我们调用了一个没有定义的函数w，编译器就会报错，除非提前声明函数原型，因此，如果要把main函数写在w函数前面，需要先声明w函数，再定义main，最后定义 w的实现。