NOIP2001 普及组 - 数的计算：算法详解及 C++ 代码

题目描述

给出自然数 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³。

算法思路

我们可以用动态规划来解决这个问题。设 dp[i] 表示以 i 为结尾的合法数列个数。那么，状态转移方程为：

dp[i] = ∑ dp[j] (j ≤ i/2)

也就是说，以 i 为结尾的合法数列，可以由所有以 i/2 或更小的数为结尾的合法数列扩展而来。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, ans = 0;
    cin >> n;
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i / 2; ++j) {
            dp[i] += dp[j];
        }
    }
    cout << dp[n] << endl;
    return 0;
}

代码优化

上面的代码可以进一步优化。由于我们只需要最后的结果 dp[n]，不需要保存所有 dp[i] 的值，因此可以使用滚动数组进行优化，将空间复杂度降为 O(1)。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, ans = 0;
    cin >> n;
    int dp = 1;
    for (int i = 2; i <= n; ++i) {
        ans = 0;
        for (int j = 1; j <= i / 2; ++j) {
            ans += dp;
        }
        dp = ans;
    }
    cout << dp << endl;
    return 0;
}

总结

本文详细讲解了 NOIP2001 普及组第一题“数的计算”的算法思路和 C++ 代码实现，并提供了优化技巧。希望本文能够帮助您更好地理解和解决类似的问题。