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

分手后的思念是犯贱 2022-09-07 01:20 270阅读 0赞

# 题目 #

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

# 思想 #

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdTE2NjU5_size_16_color_FFFFFF_t_70 1]

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

# 代码 #

#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";
    }

[Link 1]: https://www.luogu.com.cn/problem/P1028
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdTE2NjU5_size_16_color_FFFFFF_t_70]: /images/20220829/74455cf657594247a3b092e3ec23927e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdTE2NjU5_size_16_color_FFFFFF_t_70 1]: /images/20220829/ba9464fc6ec64880bd1aaa0ff27bfbbf.png