【题解】【记忆化递归】——Function

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 1
2 2 2
-1 -1 -1

输出 #1

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

提示

数据规模与约定

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

保证不包括 $-1,-1,-1$ 的输入行数 $T$ 满足 $1\le T\le 10^5$。

1.思路解析

    读完题目，很容易就可以根据题意模拟出递归函数，如下：（记得要开long long）。

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(a<b&&b<c)return w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);//缓存答案 
    else return w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
}

    但是很荣幸地打了零分。

    这是因为，这个递归函数存在大量重复调用。我们可以在一个递归函数计算完成之后，将答案缓存下来，后续只要发现这个答案计算过就直接返回。这就是记忆化递归。改动后的递归函数如下：

long long a,b,c,f[25][25][25];//用数组f缓存答案
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(f[a][b][c])return f[a][b][c];
    if(a<b&&b<c)f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);//缓存答案 
    else f[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 f[a][b][c];
}

    注意，由于w函数的返回值永远大于$1$，所以并不需要将f数组初始化为-1，直接判断是否为0就行了。

2.AC代码

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,f[25][25][25];//用数组f缓存答案
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(f[a][b][c])return f[a][b][c];
    if(a<b&&b<c)f[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);//缓存答案 
    else f[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 f[a][b][c];
}
int main()
{
    while(true)//循环输入 
    {
    scanf("%lld%lld%lld",&a,&b,&c);
    if(a==-1&&b==-1&&c==-1)break;//结束 
    printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
}
return 0;
}

喜欢就订阅此专辑吧！

【蓝胖子编程教育简介】
蓝胖子编程教育，是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务，包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式，旨在激发孩子们对编程的兴趣，培养他们的逻辑思维能力和创造力，让孩子们在轻松愉快的氛围中掌握编程知识，为未来科技人才的培养奠定坚实基础。

欢迎扫码关注蓝胖子编程教育

原文地址：https://blog.csdn.net/Pantheraonca/article/details/142675182

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！