信奥赛C提高组csp-s之搜索进阶记忆化搜索案例实践2数的计算题目描述给出正整数n nn要求按如下方式构造数列只有一个数n nn的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数但是这个正整数不能超过该数列最后一项的一半可以得到一个新的合法数列。请你求出一共有多少个合法的数列。两个合法数列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输入 16输出 16说明/提示样例 1 解释满足条件的数列为6 666 , 1 6, 16,16 , 2 6, 26,26 , 3 6, 36,36 , 2 , 1 6, 2, 16,2,16 , 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 已经计算过的结果。代码实现#includebits/stdc.husingnamespacestd;intn;intf[1005];// f[i]存储数字i能生成的数的总数-1表示未计算intdfs(intx){if(f[x]!-1)returnf[x];// 记忆化已计算直接返回intsum1;// 1表示原数本身不作任何处理for(inti1;ix/2;i){sumdfs(i);// 递归计算加上每个可能数字后的方案数}returnf[x]sum;// 存备忘录并返回}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinn;memset(f,-1,sizeof(f));// 初始化备忘录coutdfs(n)endl;return0;}功能分析模块功能说明备忘录数组f[1005]存储每个数字对应的方案总数-1表示未计算dfs(x)递归计算数字 x 能生成的所有数的总数累加循环枚举所有不超过 x/2 的自然数递归计算它们的方案数并累加原数计入sum 初始化为 1代表“不作任何处理”的情况时间优化通过记忆化每个数字只计算一次复杂度 O(n²) → O(n)更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}