NOIP2001 普及组 - 数的计算：解题思路与代码实现

NOIP2001 普及组 - 数的计算：解题思路与代码实现

题目描述

给定一个自然数 n，你需要构造一个数列，满足以下规则：

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

你需要计算出所有可能的合法数列的数量。两个合法数列不同，当且仅当它们的长度不同，或存在一个正整数 i（i 不超过数列长度），使得这两个数列的第 i 项不同。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

6

样例输出 #1

6

提示

样例 1 解释

满足条件的数列为：

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

数据规模与约定

对于所有的测试点，保证 1 ≤ n ≤ 10^3。

解题思路

本题可以使用递归或动态规划来解决。我们以递归为例来解释：

1. 递归的边界条件: 当我们已经构造出一个数列，并且当前的数字已经大于 n 时，说明我们找到了一个合法数列，返回 1。
2. 递归的递推关系: 假设当前我们已经构造了一个数列，最后一个数字是 last，当前的数字是 x。 为了构造新的合法数列，我们可以枚举在数列末尾添加的数字 i。 i 的取值范围是 1 到 last/2（因为 i 不能超过 last 的一半）。

C++ 代码实现

#include <iostream>
using namespace std;
int n, ans;
void dfs(int x, int last) {
    if (x > n) {
        ans++;
        return;
    }
    for (int i = last; i >= 1; i--)
        if (x + i <= n * 2)
            dfs(x + i, i);
}
int main() {
    cin >> n;
    dfs(1, n);
    cout << ans << endl;
    return 0;
}

总结

本题考察了递归或动态规划的应用。理解题意、找到递归的边界条件和递推关系是解决问题的关键。希望本文能够帮助你更好地理解并解决这道题目。