[NOIP 2001 普及组] 数的计算

题意

从一个数 n 开始构造数列。每次可以在末尾加入一个正整数，但新加入的数不能超过当前最后一项的一半。问一共有多少个合法数列。

思路

设 dp[x] 表示以 x 作为当前最后一项时，后面还能形成多少种合法后续。

最短的数列是只保留 x 本身，所以先有 1 种。

如果继续添加，新数可以是：

text

11..x//2

因此：

text

1dp[x] = 1 + dp[1] + dp[2] + ... + dp[x//2]

从小到大计算 dp[x]，答案是 dp[n]。

小 DP 表

x	可接的新数	dp[x]
1	无	1
2	1	2
3	1	2
4	1,2	4
5	1,2	4
6	1,2,3	6

样例 n=6，答案为 6。

Python 知识

用列表 dp = [0] * (n + 1) 保存递推结果。
value // 2 是整数除法，对应“不超过一半”。
从小到大填表，可以保证用到的 dp[next_value] 已经算好。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md

代码

python

1
2
3
4
5
6
7
8
9n = int(input())

dp = [0] * (n + 1)
for value in range(1, n + 1):
    dp[value] = 1
    for next_value in range(1, value // 2 + 1):
        dp[value] += dp[next_value]

print(dp[n])

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int dp[1005];

int main() {
    cin >> n;
    for (int x = 1; x <= n; x++) {
        dp[x] = 1; // 只有 x 本身
        for (int nxt = 1; nxt <= x / 2; nxt++)
            dp[x] += dp[nxt];
    }
    cout << dp[n] << endl;
    return 0;
}

Pythonic 写法

dp + sum 切片：

python

1
2
3
4
5n = int(input())
dp = [0] * (n + 1)
for value in range(1, n + 1):
    dp[value] = 1 + sum(dp[1:value // 2 + 1])
print(dp[n])

复杂度

时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ 。n <= 1000 可以通过。

总结

这题的状态不是“整条数列”，而是“当前最后一个数是多少”。抓住这一点后递推很直接。

[NOIP 2001 普及组] 数的计算

目录

题意

思路

小 DP 表

Python 知识

代码

Pythonic 写法

复杂度

总结