NOIP2001 普及组 - 数的计算：算法分析与代码实现

NOIP2001 普及组 - 数的计算：算法分析与代码实现

题目描述

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

6

样例输出 #1

6

提示

样例 1 解释

满足条件的数列为：

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

数据规模与约定

对于全部的测试点，保证 1 ≤ n ≤ 10³。

算法分析

这道题可以使用动态规划算法来解决。我们可以用 f(n, last) 表示以 n 为起点，最后一个数字为 last 的合法数列个数。那么，我们可以得出状态转移方程：

f(n, last) = 1 + ∑<sub>i=1</sub><sup>min(n, last/2)</sup> f(n-i, i)

该方程表示，从 n 开始，可以添加 1 到 min(n, last/2) 的数字作为下一个数字，并递归地计算以 n-i 为起点，最后一个数字为 i 的合法数列个数。

代码实现

#include <iostream>
using namespace std;

int f(int n, int last) {
    if (n == 0) return 1;
    int ans = 0;
    for (int i = 1; i <= last / 2 && i <= n; i++) {
        ans += f(n - i, i);
    }
    return ans + 1;
}

int main() {
    int n;
    cin >> n;
    cout << f(n, n) << endl;
    return 0;
}

总结

本题的解题思路是使用动态规划算法，通过递归的方式来计算所有合法的数列个数。代码实现简单易懂，可以帮助读者更好地理解动态规划算法的应用。

感谢 @dbxxx 对本题情况的反馈，原题面的问题见本贴。