首页 > 其他分享 >D - Yet Another Recursive Function -- ATCODER

D - Yet Another Recursive Function -- ATCODER

时间:2022-10-31 22:57:03浏览次数:56  
标签:Function ATCODER thirf Recursive mem top long pile half

D - Yet Another Recursive Function

https://atcoder.jp/contests/abc275/tasks/abc275_d

 

思路

动态规划问题。

第一印象使用函数递归调用实现, 但刚开始担心会爆栈,因为n很大会产生很多次递归调用层数,

所以,最开始考虑使用stack来计算,  但是stack无法回溯,不能做memerization。

所以又回到 函数递归调用方法, 测算最大调用层数最多18,没有问题。

故使用递归调用方法。

 

Code

https://atcoder.jp/contests/abc275/submissions/36123040

long long n;
map<long long, long long> mem;
//stack<long long> pile;
 
long long dp(long long n){
    if (n <= 0){
        return 1;
    }
    
    if (mem[n] > 0){
        return mem[n];
    }
    
    long long half = n / 2;
 
    long long thirf = n / 3;
 
    long long ret = dp(half) + dp(thirf);
 
    if (mem[n] == 0){
        mem[n] = ret;
    }
 
    return ret;
}
 
int main()
{
    cin >> n;
//    
//    long long sum = 0;
//    
//    pile.push(n);
//    while(!pile.empty()){
//        long long top = pile.top();
//        pile.pop();
//        
//        if (top == 0) {
//            sum++;
//            continue;
//        }
//        
//        long long half = top / 2;
//        pile.push(half);
//        
//        long long thirf = top / 3;
//        pile.push(thirf);
//    }
 
    cout << dp(n) << endl;
 
    return 0;
}
 

 

标签:Function,ATCODER,thirf,Recursive,mem,top,long,pile,half
From: https://www.cnblogs.com/lightsong/p/16846183.html

相关文章

  • 洛谷 P1464 Function(dfs+记忆化搜索)
    https://www.luogu.com.cn/problem/P1464单个返回条件的时候,直接return多个返回条件的时候,采用记忆化搜索思想,边存储边继续往下搜索中间穿插记忆化判断,如果之前有过此......
  • AtCoder Beginner Contest 275 D~F
    D-YetAnotherRecursiveFunction思路:直觉需要用到的数字大多数是重复的,所以记忆化了一下,测了一下1e18的数据,跑的飞快,直接交了,6ms。#include<bits/stdc++.h>#def......
  • C - Counting Squares -- ATCODER
    C-CountingSquareshttps://atcoder.jp/contests/abc275/tasks/abc275_c参考:https://atcoder.jp/contests/abc275/submissions/36103954 思路首先不能使用暴力穷......
  • 【atcoder 293 F - Erase Subarrays】【动态规划】
    importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;publicclassMain{publicstaticvoidmain(String[]args)......
  • Atcoder ABC 273、 272、271的C、 D
    ABC273C(K+1)-thLargestNumber题意:给予你一个长度是N的数组a,对于每一个k(0,1,2,...N-1),完成一下问题:找到1~N中的数字a[i],找到大于a[i]的数目恰好是k个不同数的......
  • Atcoder试题乱做 Part5
    名言,解决不了题目,那就解决你自己./ybyb\(\text{[ARC136E]Non-coprimeDAG}\)\(\color{blue}{\text{[NORMAL]}}\)考虑\(i\)什么时候能到达\(j\),令\(f_x\)......
  • 【atcoder 293 E - Sugoroku 4】【动态规划,递推】
    importjava.io.IOException;importjava.util.Arrays;importjava.util.Scanner;publicclassMain{staticintn,m,k;staticintMOD=998244353;......
  • C++11绑定器bind及function机制
    前言之前在学muduo网络库时,看到陈硕以基于对象编程的方式,大量使用boost库中的bind和function机制,如今,这些概念都已引入至C++11,包含在头文件<functional>中。本篇文章主要......
  • AtCoder Beginner Contest 275 E F
    E-Sugoroku4题意:从0走到n,有k次操作,每次会丢出一个骰子,骰子上的数字为\([1,m]\),等概率出现问到达n的概率思路:\(dp[i][k]\)表示用了k次操作到达位置i的概......
  • Atcoder Beginner Contest 275(A~F)
    我好菜啊……又没切掉F,40+min切掉A~E成功滚粗。希望能越打越好吧……赛时A求序列最大值,B简单计算,C数正方形,跳过。D递推不太行,N的范围有点大。但是除法的转移......