洛谷刷题C++语言 | P1464 Function

学习C++从娃娃抓起！记录下洛谷C++学习和备考过程中的题目，记录每一个瞬间。

附上汇总贴：洛谷刷题C++语言 | 汇总_热爱编程的通信人的博客-CSDN博客

【题目描述】

对于一个递归函数 w(a,b,c)

• 如果 a≤0 或 b≤0 或 c≤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
2 2 2
-1 -1 -1

【输出样例】

w(1, 1, 1) = 2
w(2, 2, 2) = 4

【代码详解】

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a, b, c;
int w1[25][25][25]={0};
int 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 (w1[a][b][c]!=0) return w1[a][b][c];
    if (a<b && b<c) {
        w1[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
    } 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()
{
    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