信奥赛C++提高组csp-s之搜索进阶（记忆化搜索案例实践2）

信奥赛C++提高组csp-s之搜索进阶（记忆化搜索案例实践2）

数的计算

题目描述

给出正整数n nn，要求按如下方式构造数列：

1. 只有一个数n nn的数列是一个合法的数列。
2. 在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。

请你求出，一共有多少个合法的数列。两个合法数列a , b a, ba,b不同当且仅当两数列长度不同或存在一个正整数i ≤ ∣ a ∣ i \leq |a|i≤∣a∣，使得a i ≠ b i a_i \neq b_iai​=bi​。

输入格式

输入只有一行一个整数，表示n nn。

输出格式

输出一行一个整数，表示合法的数列个数。

输入输出样例 1

输入 1

6

输出 1

6

说明/提示

样例 1 解释

满足条件的数列为：

• 6 66
• 6 , 1 6, 16,1
• 6 , 2 6, 26,2
• 6 , 3 6, 36,3
• 6 , 2 , 1 6, 2, 16,2,1
• 6 , 3 , 1 6, 3, 16,3,1

数据规模与约定

对于全部的测试点，保证1 ≤ n ≤ 10 3 1 \leq n \leq 10^31≤n≤103。

思路分析

题目大意：

输入自然数 n，可以对它进行以下操作：

• 不作任何处理
• 在它左边加上一个不超过原数一半的自然数
• 加上数后继续按此规则处理
  求所有可能的数的个数（包含原数本身）。

分析思路：

令f[x]表示数字 x 能生成的数的总数（包含 x 自身）。根据规则：

• x 可以不作处理 → 1 种（即 x 本身）
• 可以在左边加上 1, 2, …, floor(x/2) 作为新的数，这些新数又可以继续生成

所以f[x] = 1 + f[1] + f[2] + ... + f[floor(x/2)]

递归计算时会有大量重复计算，例如f[6]需要f[3]，f[5]也需要f[2]等，因此需要用数组记录每个 x 已经计算过的结果。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn;intf[1005];// f[i]存储数字i能生成的数的总数，-1表示未计算intdfs(intx){if(f[x]!=-1)returnf[x];// 记忆化：已计算直接返回intsum=1;// 1表示原数本身（不作任何处理）for(inti=1;i<=x/2;i++){sum+=dfs(i);// 递归计算加上每个可能数字后的方案数}returnf[x]=sum;// 存备忘录并返回}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;memset(f,-1,sizeof(f));// 初始化备忘录cout<<dfs(n)<<endl;return0;}

功能分析

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}