一本通1316 数的计数

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iterator>
#include <vector>
#define maxn 10000005
typedef long long ll;
using namespace std;
int n;

/*
 普通递归时间复杂度太高
 改用记忆化搜索
 */ 
//ll ans=1;
//void fun(int n){
//    if(n/2==0){
//        
//        return;
//    }else{
//        for(int i=1;i<=n/2;i++){
//            ans++;
//        //    cout<<i<<endl;
//            fun(i);
//        }
//    }
//}
int h[1001]; 
void fun(int n){
    if(h[n]!=-1) return;
    h[n]=1;
    for(int i=1;i<=n/2;i++){
        fun(i);
        h[n]=h[n]+h[i];
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        h[i]=-1;
    }
    fun(n);
    cout<<h[n]; 
    return 0;
}

 

上一篇:LuoguP1635 WJMZBMR打osu! / Easy 题解


下一篇:【模板】后缀排序