P1028 [NOIP 2001 普及组] 数的计算
题目描述
给出正整数 \(n\)，要求按如下方式构造数列：
- 只有一个数 \(n\) 的数列是一个合法的数列。
- 在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。
请你求出，一共有多少个合法的数列。两个合法数列 \(a, b\) 不同当且仅当两数列长度不同或存在一个正整数 \(i \leq |a|\)，使得 \(a_i \neq b_i\)。
输入格式
输入只有一行一个整数，表示 \(n\)。
输出格式
输出一行一个整数，表示合法的数列个数。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
样例 1 解释
满足条件的数列为：
- \(6\)
- \(6, 1\)
- \(6, 2\)
- \(6, 3\)
- \(6, 2, 1\)
- \(6, 3, 1\)
数据规模与约定
对于全部的测试点，保证 \(1 \leq n \leq 10^3\)。
说明
本题数据来源是 NOIP 2001 普及组第一题，但是原题的题面描述和数据不符，故对题面进行了修改，使之符合数据。原题面如下，谨供参考：
我们要求找出具有下列性质数的个数（包含输入的正整数 \(n\)）。
先输入一个正整数 \(n\)（\(n \le 1000\)），然后对此正整数按照如下方法进行处理：
- 不作任何处理；
- 在它的左边拼接一个正整数，但该正整数不能超过原数，或者是上一个被拼接的数的一半；
- 加上数后，继续按此规则进行处理，直到不能再加正整数为止。
Tip
📌 题目分析
给定序列的初始值 n（最大 1000）。
每次可以在序列末尾追加一个新数字，要求新数字必须 小于等于 上一个数字的一半。
求一共能构造出多少种不同的合法数列。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 状态定义
我们可以定义一个数组：
题目要求的是以 n 为开头的数列个数，也就是求 dp[n]。
2️⃣ 状态转移方程
对于任意一个数字 i，它构成的合法数列可以分为两类：
* 只有它自己本身： 例如数列 {i}，这算作 1 种情况。
* 后面追加了数字： 可以在后面追加 1 到 i/2 之间的任意一个数字 j。只要追加了 j，后面能构成的数列个数就完全等同于 dp[j]。
因此，递推公式为： \(dp[i] = 1 + \sum_{j=1}^{\lfloor i/2 \rfloor} dp[j]\)
3️⃣ 边界与计算顺序
最小的数字是 1，以 1 开头的合法数列只有 {1}，因此：
由于 dp[i] 的计算依赖于比它小的 dp[j]，所以我们只需要从小到大遍历 1 到 n 进行计算即可。
4️⃣ 时间复杂度
外层循环 n 次，内层循环最多 n/2 次。
整体时间复杂度为 O(n²)。
对于最大 1000 的数据规模，计算量仅为几十万级别，在 1 秒时限内绰绰有余。
💻 C++代码
#include <iostream>
#include <vector>
using namespace std;
// 使用 long long 防止累加过程中溢出
long long dp[1005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// 边界条件：以 1 开头的数列只有 1 种
dp[1] = 1;
// 从 2 开始从小到大递推
for (int i = 2; i <= n; i++) {
dp[i] = 1; // 1 代表只有数字 i 本身的这一种数列
for (int j = 1; j <= i / 2; j++) {
dp[i] += dp[j]; // 累加所有合法分支的数列个数
}
}
cout << dp[n] << "\n";
return 0;
}
⚠️ 易错点
❌ 1. 忘记算上数字本身的 1 种情况
递推时必须初始化 dp[i] = 1。
很多初学者会写成 dp[i] = sum(dp[j])，这样漏掉了不追加任何数字（只有 {i} 本身）的基础情况。
❌ 2. 纯暴力递归导致超时 (TLE)
如果直接写一个递归函数 dfs(n)，并在里面用 for 循环继续调用 dfs(i) 而不记录结果，会产生大量的重复计算。
必须使用 DP 数组保存已经算过的结果（即记忆化），或者像上面代码那样直接从小到大递推。
❌ 3. 循环范围写错
题目规定追加的数字不能超过上一项的一半。
内层循环必须写成 j <= i / 2，漏掉等号会导致结果偏小。
🚀 一句话总结
🔥 补充
其实这道题还有一个 O(n) 的终极数学优化思路（利用前缀和的规律）：
如果仔细观察奇偶性，会发现递推式可以被极大化简：
* 当 i 为奇数时： i / 2 向下取整的结果和 (i - 1) / 2 完全一样。所以 dp[i] = dp[i-1]。
* 当 i 为偶数时： 比 dp[i-1] 刚好只多出了一项 dp[i/2]。所以 dp[i] = dp[i-1] + dp[i/2]。
如果使用这个规律，内层循环可以直接省掉，代码变成：
dp[1] = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 1) {
dp[i] = dp[i - 1];
} else {
dp[i] = dp[i - 1] + dp[i / 2];
}
}
O(n)，也是进阶选手最喜欢用的解法。