建设网站询价对比表模板,seo网站营销推广,东城网站建设公司,佛山网站优化美姿姿seo题解#xff1a;ABC275D - Yet Another Recursive Function
题目
链接#xff1a;Atcoder。
链接#xff1a;洛谷。
难度
算法难度#xff1a;普及。
思维难度#xff1a;入门。
调码难度#xff1a;入门。
综合评价#xff1a;简单。
算法
记忆化深度优先搜索…题解ABC275D - Yet Another Recursive Function
·题目
链接Atcoder。
链接洛谷。
·难度
算法难度普及。
思维难度入门。
调码难度入门。
综合评价简单。
·算法
记忆化深度优先搜索stl_map。
·思路
用map来记录每一个已经搜索到状态f(x)的答案并以此实现记忆化搜索并通过递归式“f(x)f(x/2)f(x/3)/表示整除即正常做除法之后再向下取整”求出答案。
·代价
虽然状态总共有1000000000000000000个状态但是实际上用到的状态十分稀疏几乎是log级别的所以可以卡过。
·细节
状态f(0)可以不记忆化因为直接返回1就行。
·代码
AC。
#includebits/stdc.h
using namespace std;
maplong long,long longans;
long long n0;
long long f(long long num);
int main(){scanf(%lld,n);printf(%lld\n,f(n));return 0;
}
long long f(long long num){if(num0){return 1;}if(ans[num]!0){return ans[num];}long long retf(num/2)f(num/3);ans[num]ret;return ret;
}
·注意
①开long long。
