【记忆化搜索】ABC275 D - Yet Another Recursive Function

淩亂°似流年 2024-03-24 14:39 50阅读 0赞

这题虽然简单，但是告诉了我们记忆化搜索的复杂度是怎么考虑的：

考虑所有的状态被去重后的结果，即所有的状态只被访问一次的结果

[D - Yet Another Recursive Function (atcoder.jp)][D - Yet Another Recursive Function _atcoder.jp]

题意：

![37639dd0ab3d403ebaa79b6b3f8c2daa.png][]

思路：

直接记忆化搜索即可，数组开不下了就用map

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long 
    const int mxn=1e2+10;
    const int mxe=5e4+10;
    const int mod=1e9+7;
    
    
    map<int,int> mp;
    int n;
    int F(int x){
        if(mp.count(x)) return mp[x];
        if(x==0) return mp[x]=1;
        return mp[x]=F(x/2)+F(x/3);
    }
    void solve(){
        cin>>n;
        cout<<F(n)<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[D - Yet Another Recursive Function _atcoder.jp]: https://atcoder.jp/contests/abc275/tasks/abc275_d
[37639dd0ab3d403ebaa79b6b3f8c2daa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/5c31f4f29e724b489a4f146489678727.png

发表评论取消回复

表情：

评论列表（有 0 条评论，50人围观）

还没有评论，来说两句吧...

相关阅读

相关 ABC246 D - 2-variable Function

很重要的一点就是，看到代数式要很自然地去推导数据范围 [D - 2-variable Function (atcoder.jp)][D - 2-variable Functi

客官°小女子只卖身不卖艺/ 2024年03月24日 15:56/ 0 赞/ 6 阅读

相关【记忆化搜索】ABC275 D - Yet Another Recursive Function

这题虽然简单，但是告诉了我们记忆化搜索的复杂度是怎么考虑的：考虑所有的状态被去重后的结果，即所有的状态只被访问一次的结果 [D - Yet Another Recursi

淩亂°似流年/ 2024年03月24日 14:39/ 0 赞/ 51 阅读

相关【分段DP】ABC275 F

一万年没写DP了这么简单的DP我居然没写出来 [F - Erase Subarrays (atcoder.jp)][F - Erase Subarrays _atcode

叁歲伎倆/ 2024年03月22日 09:11/ 0 赞/ 50 阅读

相关【CF1197D】Yet Another Subarray Problem

Description [【CF1197D】Yet Another Subarray Problem][CF1197D_Yet Another Subarray Prob

阳光穿透心脏的1/2处/ 2023年06月05日 08:54/ 0 赞/ 20 阅读

相关记忆化搜索——滑雪

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 87592 Accepted: 32835 Des

女爷i/ 2022年08月21日 01:20/ 0 赞/ 204 阅读

相关 POJ 1579-Function Run Fun（记忆化搜索-递归）

Function Run Fun <table> <tbody> <tr> <td><strong>Time Limit:</strong> 10

- 日理万妓/ 2022年06月15日 22:22/ 0 赞/ 175 阅读

相关 ACM 记忆化搜索 Function Run Fun & FatMouse and Cheese

滴，集训第四天打卡。今天是记忆化搜索和字典树... 记忆话搜索可以举一反三..字典树看了一下午几乎是绝望的.. 所以下一篇会是字典树专题... POJ 1579 Fu

ゝ一纸荒年。/ 2022年06月12日 09:36/ 0 赞/ 183 阅读

相关动态规划记忆化搜索--Function Run Fun

Function Run Fun Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

缺乏、安全感/ 2022年05月31日 00:29/ 0 赞/ 197 阅读

相关滑雪【记忆化搜索】

滑雪 Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Mich

分手后的思念是犯贱/ 2022年05月25日 04:22/ 0 赞/ 209 阅读

相关滑雪 ————记忆化搜索

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道

￡神魔★判官ぃ/ 2022年05月17日 11:37/ 0 赞/ 171 阅读