【NOIP真题】2001 数的计算 luogu-P1028 | 适用于 GESP四级 / CSP-J 练习

从一个正整数出发，每次在左侧追加一个不超过其一半的正整数，这种层层衍生的规则自然勾勒出了一棵递推分支树。洛谷 P1028 [NOIP2001 普及组]《数的计算》是一道经典的树形衍生计数问题。表面上看，它可以通过深度优先搜索或纯递归直接模拟生成过程；但随着数值增大，重叠子问题会导致朴素递归呈指数级爆炸超时。通过前缀和优化将状态递推复杂度压缩到 ，不仅是理解记忆化搜索与动态规划分水岭的绝佳载体，也是 GESP 四级跨越至五级进阶的核心思维跃迁。

luogu-P1028 [NOIP2001 普及组] 数的计算

🔗 洛谷原题传送门：luogu-P1028 [NOIP2001 普及组] 数的计算

🔹 题目描述

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

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

请你求出，一共有多少个合法的数列。两个合法数列  不同当且仅当两数列长度不同或存在一个正整数 ，使得 。

🔹 输入格式

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

🔹 输出格式

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

🔹 输入输出样例

输入 #1

输出 #1

🔹 说明/提示

样例 1 解释

满足条件的数列为：

数据规模与约定

对于全部的测试点，保证 。

🔹 题目深度剖析

1. 规则转化与数学建模

题目要求以一个给定的自然数  开头，每次可以在当前数列末尾添加一个正整数 ，且该正整数必须满足：

我们需要统计从数字  出发，能够产生的所有合法数列的总数量。

观察构造过程可以发现：后续允许添加的数字集合仅取决于当前数列的末尾数字，而与更早之前添加了哪些数完全无关。这正是典型的“无后效性”特征。

我们定义状态：

• 设  表示以正整数  为开头的合法数列的总个数。

对于以  开头的任意合法数列，其构成方式分为两类：

1. 单元素数列
   ：仅由  本身构成的数列，方案数为 ；
2. 多元素数列
   ：在  后面拼接一个合法正整数 （满足 ）。一旦确定了第二项为 ，由于后续的拼接规则完全由  及其后续末尾项决定，因此以  为开头的合法数列共有  种，每一种都可以无缝拼接在  的后面形成以  开头的新合法数列。

综合以上两种情况，我们可以得到严密的数学递推关系式：

边界条件非常直观：

• 当  时，，求和项为空，故 （仅有数列 ）；
• 当  时，，（数列为 ）；
• 当  时，，（数列为 ）；
• 当  时，，（与样例完全一致）。

2. 算法演进：从指数爆炸到线性递推

在等级考试和信奥入门阶段，许多同学初次接触本题时容易直接写出无记忆化的纯递归函数：

为什么朴素递归会严重超时？

如果对  运行上述纯递归代码，计算 dfs(1000) 需要调用 dfs(500)、dfs(250) 等，而计算 dfs(999) 同样会重复调用 dfs(499)、dfs(249)……子问题被重复展开了天文数字般的次数，其调用树的时间复杂度呈指数级爆炸（），程序将直接卡死并导致 TLE（Time Limit Exceeded）。

自底向上的递推 DP 方案

因为计算  只需要依赖已知比它小的子问题答案 ，我们完全可以采用**自底向上（Bottom-Up）**的双层循环递推：

• 外层循环遍历  从  到 ；
• 内层循环遍历  从  到 ，累加已算出的 ；
• 状态计算完毕后直接保存在数组 f[i] 中。

在  的数据规模下，内层总计算次数仅为  次加法，现代计算机可在不到  毫秒内瞬时算出！

3. 数据边界与整型溢出防范

在编写算法题解时，必须对数值上限保持高度敏锐：

• 当  时，经过递推计算得出的 ；
• 标准 32 位有符号整数 int 的上限为 ；
• 可以看出， 已经达到了约 ，与 int 最大上限仅差不到 ！

如果在累加过程中稍有微小改动或拓展，极易触发 32 位整型上溢。因此，遵循 CCF GESP 及 CSP 优良规范，本题推荐使用 64 位整型 long long 存储状态数组，彻底消除边界溢出隐患。

4. 规范避坑与实现要点

1. 严禁局部变长数组（VLA）
   ： 
• 严禁在 main() 函数内部声明形如 long long f[n + 1]; 的局部数组；
• 规范做法是在全局数据区声明固定常量与数组：const int MAXN = 1005; long long f[MAXN];。全局数组位于静态存储区，自动初始化为全 0。
2. 标准竞赛输入输出
   ： 
• 保持主函数输入逻辑干净清晰，直接 cin >> n;，不引入冗余的防御性判断代码；
• 无需复杂的快读模板，基础 cin/cout 即可轻量级秒杀本题。

🔹 完整参考代码 (C++11)