【洛谷 P1464】Function 题解(递归+记忆化搜索)

简介: 该题目定义了一个递归函数$w(a,b,c)$,具有特定的终止条件和递归规则。当$a, b, c$任一值小于等于0或大于20时,函数有特殊返回值。否则,根据$a, b, c$的相对大小关系应用不同的递归计算。给定输入是一系列的三元组$(a, b, c)$,以$-1,-1,-1$结束。程序使用记忆化搜索优化递归调用,避免重复计算。样例输入输出展示了如何计算$w(1, 1, 1)$和$w(2, 2, 2)$。

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$ 结束。

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

输出格式

输出若干行,每一行格式:

w(a, b, c) = ans

注意空格。

样例 #1

样例输入 #1

1 1 1
2 2 2
-1 -1 -1

样例输出 #1

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

思路

AC代码

#include <iostream>
#include <cstring>
using namespace std;
#define AUTHOR "HEX9CF"
#define ll long long

const int maxn = 55;

ll mem[maxn][maxn][maxn];

ll w(ll x, ll y, ll z){
   
    if(x <= 0 || y <= 0 || z <= 0){
   
        return 1;
    }
    if(x > 20 || y > 20 || z > 20){
   
        return w(20, 20, 20);
    }
    if(mem[x][y][z]){
   
        return mem[x][y][z];
    }
    return mem[x][y][z] = w(x - 1, y, z) + w(x - 1, y - 1, z) + w(x - 1, y, z - 1) - w(x - 1, y - 1, z - 1);
}

int main(){
   
    ll a, b, c;
    memset(mem, 0, sizeof(mem));
    while (cin >> a >> b >> c){
   
        if(!~a && !~b && !~c){
   
            return 0;
        }
        printf("w(%ld, %ld, %ld) = %ld\n", a, b, c, w(a, b, c));
    }
    return 0;
}
目录
相关文章
|
搜索推荐 Java API
基于OpenAI Function Call 结合Lucene实现本地化的知识搜索
这是一个OpenAI Function 接入的Demo,通过Lucene+OpenAI实现个人知识库,但是目前只有服务端,没有页面之类的东西,并且实现的非常简单,所以只能当做一个Demo使用。
569 0
基于OpenAI Function Call 结合Lucene实现本地化的知识搜索
|
人工智能 Java
Elasticsearch:使用 function_score 中的weight和gauss衰减函数定制搜索结果的分数
Elasticsearch:使用 function_score 中的weight和gauss衰减函数定制搜索结果的分数
|
缓存 算法 搜索推荐
【Elastic Engineering】Elasticsearch:使用 function_score 及 script_score 定制搜索结果的分数
Elasticsearch:使用 function_score 及 script_score 定制搜索结果的分数
855 0
【Elastic Engineering】Elasticsearch:使用 function_score 及 script_score 定制搜索结果的分数
|
6月前
|
人工智能 Python
083_类_对象_成员方法_method_函数_function_isinstance
本内容主要讲解Python中的数据类型与面向对象基础。回顾了变量类型(如字符串`str`和整型`int`)及其相互转换,探讨了加法在不同类型中的表现。通过超市商品分类比喻,引出“类型”概念,并深入解析类(class)与对象(object)的关系,例如具体橘子是橘子类的实例。还介绍了`isinstance`函数判断类型、`type`与`help`探索类型属性,以及`str`和`int`的不同方法。最终总结类是抽象类型,对象是其实例,不同类型的对象有独特运算和方法,为后续学习埋下伏笔。
111 7
083_类_对象_成员方法_method_函数_function_isinstance
|
6月前
|
Python
[oeasy]python086方法_method_函数_function_区别
本文详细解析了Python中方法(method)与函数(function)的区别。通过回顾列表操作如`append`,以及随机模块的使用,介绍了方法作为类的成员需要通过实例调用的特点。对比内建函数如`print`和`input`,它们无需对象即可直接调用。总结指出方法需基于对象调用且包含`self`参数,而函数独立存在无需`self`。最后提供了学习资源链接,方便进一步探索。
119 17
|
6月前
|
人工智能 Python
[oeasy]python083_类_对象_成员方法_method_函数_function_isinstance
本文介绍了Python中类、对象、成员方法及函数的概念。通过超市商品分类的例子,形象地解释了“类型”的概念,如整型(int)和字符串(str)是两种不同的数据类型。整型对象支持数字求和,字符串对象支持拼接。使用`isinstance`函数可以判断对象是否属于特定类型,例如判断变量是否为整型。此外,还探讨了面向对象编程(OOP)与面向过程编程的区别,并简要介绍了`type`和`help`函数的用法。最后总结指出,不同类型的对象有不同的运算和方法,如字符串有`find`和`index`方法,而整型没有。更多内容可参考文末提供的蓝桥、GitHub和Gitee链接。
127 11
|
12月前
|
JavaScript
箭头函数与普通函数(function)的区别
箭头函数是ES6引入的新特性,与传统函数相比,它有更简洁的语法,且没有自己的this、arguments、super或new.target绑定,而是继承自外层作用域。箭头函数不适用于构造函数,不能使用new关键字调用。
|
11月前
|
中间件 Docker Python
【Azure Function】FTP上传了Python Function文件后,无法在门户页面加载函数的问题
通过FTP上传Python Function至Azure云后,出现函数列表无法加载的问题。经排查,发现是由于`requirements.txt`中的依赖包未被正确安装。解决方法为:在本地安装依赖包到`.python_packages/lib/site-packages`目录,再将该目录内容上传至云上的`wwwroot`目录,并重启应用。最终成功加载函数列表。
113 0

热门文章

最新文章