【GESP/CSP练习】GESP四级 / CSP-J 题解：luogu-P1028 [NOIP2001 普及组] 数的计算

NOIP 2001 普及组第一题，洛谷 P1028。本题是算法竞赛与考级中学习简单递归、记忆化与线性递推模型的标志性启蒙经典试题，被标准收录于 CCF GESP 四级认证考纲（简单递归与递推初步考点）及 CSP-J 普及组核心基础必做题单。题目核心考察如何将数列构造规则抽象为自底向上的子问题状态转移方程，并理解直接纯递归导致的指数级重复计算瓶颈，进而利用数组递推（或记忆化搜索）实现 $\mathcal{O}(n^2)$ 乃至 $\mathcal{O}(n)$ 的高效求解。题目难度⭐☆☆☆☆，洛谷难度等级评定为普及-。

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

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

题目要求

题目描述

给出自然数 $n$，要求按如下方式构造数列：

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

请你求出，一共有多少个合法的数列。两个合法数列 $a, b$ 不同当且仅当两数列长度不同或存在一个正整数 $i \leq |a|$，使得 $a_i \neq b_i$。

输入格式

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

输出格式

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

输入输出样例 #1

样例输入 #1

16
2

样例输出 #1

16
2

说明/提示

样例 1 解释

满足条件的数列为：

• $6$
• $6, 1$
• $6, 2$
• $6, 3$
• $6, 2, 1$
• $6, 3, 1$

数据规模与约定

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

题目深度剖析

1. 规则转化与数学建模

题目要求以一个给定的自然数 $n$ 开头，每次可以在当前数列末尾添加一个正整数 $x$，且该正整数必须满足： $1 \le x \le \lfloor \frac{\text{末尾项}}{2} \rfloor$

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

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

我们定义状态：

• 设 $f(i)$ 表示以正整数 $i$ 为开头的合法数列的总个数。

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

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

综合以上两种情况，我们可以得到严密的数学递推关系式： $f(i) = 1 + \sum_{j=1}^{\lfloor i / 2 \rfloor} f(j)$

边界条件非常直观：

• 当 $i = 1$ 时，$\lfloor 1/2 \rfloor = 0$，求和项为空，故 $f(1) = 1$（仅有数列 $[1]$）；
• 当 $i = 2$ 时，$\lfloor 2/2 \rfloor = 1$，$f(2) = 1 + f(1) = 1 + 1 = 2$（数列为 $[2], [2, 1]$）；
• 当 $i = 3$ 时，$\lfloor 3/2 \rfloor = 1$，$f(3) = 1 + f(1) = 1 + 1 = 2$（数列为 $[3], [3, 1]$）；
• 当 $i = 6$ 时，$\lfloor 6/2 \rfloor = 3$，$f(6) = 1 + f(1) + f(2) + f(3) = 1 + 1 + 2 + 2 = 6$（与样例完全一致）。

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

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

1// 错误示范：未经记忆化的朴素递归
2int dfs(int x) {
3    int ans = 1;
4    for (int j = 1; j <= x / 2; ++j) {
5        ans += dfs(j);
6    }
7    return ans;
8}
9

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

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

自底向上的递推 DP 方案

因为计算 $f(i)$ 只需要依赖已知比它小的子问题答案 $f(1), f(2), \dots, f[\lfloor i/2 \rfloor]$，我们完全可以采用**自底向上（Bottom-Up）**的双层循环递推：

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

在 $n \le 1000$ 的数据规模下，内层总计算次数仅为 $\sum_{i=1}^{1000} \frac{i}{2} \approx \frac{1000 \times 1000}{4} = 2.5 \times 10^5$ 次加法，现代计算机可在不到 $1$ 毫秒内瞬时算出！

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

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

• 当 $n = 1000$ 时，经过递推计算得出的 $f(1000) = 1981471878$；
• 标准 32 位有符号整数 int 的上限为 $2^{31} - 1 = 2147483647$；
• 可以看出，$1981471878$ 已经达到了约 $1.98 \times 10^9$，与 int 最大上限仅差不到 $8\%$！

如果在累加过程中稍有微小改动或拓展，极易触发 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)

1/**
2 * Problem: luogu-P1028 [NOIP2001 普及组] 数的计算
3 * Algorithm: 基础递推 (Dynamic Programming / Recurrence)
4 * Standard: C++11 (CCF GESP 官方大纲规范)
5 * Author: OneCoder
6 */
7
8#include <iostream>
9
10using namespace std;
11
12// 数据规模保证 1 <= n <= 1000
13// f[i] 表示以正整数 i 为起点的所有合法数列总数
14// 经推导 f(1000) = 1981471878，极接近 32 位有符号整型上限 (2147483647)
15// 在全局数据区开辟静态数组，杜绝局部变长数组 (VLA)，使用 long long 确保安全防溢出
16const int MAXN = 1005;
17long long f[MAXN];
18
19int main() {
20    int n;
21    // 直接读入目标正整数 n
22    cin >> n;
23
24    // 自底向上递推计算每一个子问题的解 (1 到 n)
25    for (int i = 1; i <= n; ++i) {
26        // 每个数本身作为一个单元素数列 [i]，即为 1 种合法方案
27        f[i] = 1;
28
29        // 在 i 后面可以追加的正整数 j 必须满足 1 <= j <= i / 2
30        // 追加 j 之后，后续所有以 j 为开头的合法数列均可接在其后，故累加 f[j]
31        for (int j = 1; j <= i / 2; ++j) {
32            f[i] += f[j];
33        }
34    }
35
36    // 输出以 n 开头的合法数列总数量
37    cout << f[n] << endl;
38
39    return 0;
40}
41