洛谷-----P1464 Function
Function 洛谷 -----
2023-09-14 09:13:37 时间
Function题解集合
记忆化搜索
还是把本题转化为对一棵多叉树的遍历,但是题目中也暗示我们会存在很多重复计算,那么现在关键就在于找到这些重复计算,并且想办法免去这些重复计算,下面看图:
这里假设a=b=c=3
上图中相同形状用green圈出来的部分代表着是重复计算过程,可以通过哈希容器记录保存,避免重复计算
代码:
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<numeric>
#include<string>
#include<map>
class Solution {
map<vector<long>, long> cache;
public:
int w(long a,long b,long c)
{
if (cache.find({ a,b,c }) != cache.end()) return cache[{a, b, 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 cache[{a, b, c}]=w(a,b,c-1) + w(a,b-1,c-1)-w(a,b-1,c);
return cache[{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()
{
Solution s;
int a(0), b(0), c(0);
vector<vector<long>> ret;
while (1)
{
cin >> a >> b >> c;
if (a ==-1&&b==-1&&c==-1) break;
vector<long> num = { a,b,c };
ret.emplace_back(num);
}
for (int i = 0; i < ret.size(); i++)
{
cout << "w(" << ret[i][0] << ", " << ret[i][1] << ", " << ret[i][2] << ")" << " = " << s.w(ret[i][0], ret[i][1], ret[i][2])<<endl;
}
return 0;
}
相关文章
- oracle function详解,Oracle函数用法详解「建议收藏」
- 【phpmailer】类Could not instantiate mail function / IXWebHosting空间
- ORA-29301: wrong DBMS_PITR package function/procedure order ORACLE 报错 故障修复 远程处理
- ORA-30161: A system error occurred during the OCIFile function call ORACLE 报错 故障修复 远程处理
- ORA-31601: Function string cannot be called now that fetch has begun. ORACLE 报错 故障修复 远程处理
- ORA-64126: XMLIndex Table Function: failure at the start of the function ORACLE 报错 故障修复 远程处理
- ORA-64127: XMLIndex Table Function: failure at the beginning of the function ORACLE 报错 故障修复 远程处理
- PostgreSQL HV010: fdw_function_sequence_error 报错 故障修复 远程处理
- Oracle 视图 DBA_STREAMS_TRANSFORM_FUNCTION 官方解释,作用,如何使用详细说明
- RFC_GET_FUNCTION_INTERFACE_P获取函数(function module)参数详解编程语言
- JS定义函数(function关键字)
- function.inc.php超越php
- js在定义的时候立即执行的函数表达式(function)写法
- javascript两种function的定义介绍及区别说明