【洛谷】P1028 [NOIP2001 普及组] 数的计算

题目

题目链接
题目要读两遍才能理解讲什么，主要意思就是让你找出一个数可以被分裂形成多少个数？分裂的规则是，不能比该数最左侧的数的一半儿大。

思想

主要考察递归+记忆化搜索，下面以数字6为示例，给出推理过程：

在这里插入图片描述
加上自己原本的数，那么最后的结果就是可以得到6个数。接着我们来看下数字12可以被分成多少个数？

在这里插入图片描述

可以很明显的看到，我们需要用到一个记忆化搜索的技巧，这样记录已经遍历过的数，就不用再重复递归搜索了，会大大的节约时间。

代码

#include<iostream>
using namespace std;
int res = 0;
const int maxN = 1005;
//使用记忆化搜索，否则会TLE
int record[maxN];  //记录每个数字可以拆分的个数
//返回数字num可以得到的个数 
void get_num(int num){ 
    if (num == 1) //边界条件 
        return ; // 最后这一种 
    if (record[num]!= -1){ 
        res += record[num]; 
        return ; //直接加完返回 
    }
    int start = res;
    for (int i = 1;i<= num/2;i++){  //递归循环 
        res ++;
        get_num(i);
    }
    record[num] = res- start;//记录这个数可以的次数 
}
int main(){ 
    int n;
    cin >> n;
    fill(record,record+maxN,-1); 
    get_num(n);
    cout << res + 1 <<"\n";
}