点个赞再走吧

P1028 [NOIP2001 普及组] 数的计算 题解

题目理解

我们先来理解题目要求：

• 输入一个正整数 n (n ≤ 1000)
• 从 n 开始，可以在当前数的左边拼接一个正整数
• 拼接的数不能超过原数，或者是上一个被拼接的数的一半
• 重复这个过程，直到不能再加正整数为止
• 需要统计所有满足条件的数的个数

样例分析

以 n=6 为例，满足条件的数有：

• 6
• 16 (在6左边加1，1≤6且1≤3)
• 26 (在6左边加2，2≤6且2≤3)
• 126 (在26左边加1，1≤2)
• 36 (在6左边加3，3≤6且3≤3)
• 136 (在36左边加1，1≤3)

共6个数。

解题思路

方法一：递归+记忆化（题中代码解法）

这是一个典型的递归问题，我们可以这样思考：

对于数字 n，它本身就是一个合法的数（计数+1），然后我们可以在它左边拼接数字 i，其中 i 的取值范围是 1 到 n/2。

对于每个拼接的数字 i，我们又可以继续在 i 的左边拼接数字，拼接的范围是 1 到 i/2。

这样就形成了一个递归结构。

递归函数设计：

f(x) = 以x开头的所有合法数的个数

递归关系：

f(x) = 1 + f(1) + f(2) + ... + f(floor(x/2))

其中 1 代表 x 本身，后面的求和代表在所有可能的拼接情况下产生的数的个数。

基础情况：

f(1) = 1  // 只有1本身

方法二：动态规划

我们也可以使用递推的方式，从小数字开始计算：

设 dp[i] 表示以 i 开头的所有合法数的个数

状态转移方程：

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

初始化：

dp[1] = 1

代码详细解析

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

int a[114514];  // 记忆化数组，存储已经计算过的f(x)值
int n;

int f(int x){
    // 基础情况：f(1)=1
    if(x == 1){
        return 1;
    }
    
    // 如果已经计算过f(x)，直接返回结果（记忆化）
    if(a[x] != 0) return a[x];
    
    // 计数从1开始（x本身）
    int cnt = 1;    
    
    // 遍历所有可以在左边拼接的数字i（1到x/2）
    for(int i = 1; i <= x/2; i++){
        cnt += f(i);  // 递归计算以i开头的所有合法数
    }
    
    // 将结果存入记忆化数组并返回
    a[x] = cnt;
    return cnt;
}

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

算法复杂度分析

时间复杂度： O(n²)

• 对于每个数字 i，需要计算 1 到 i/2 的和
• 通过记忆化避免重复计算

空间复杂度： O(n)

• 主要用于存储记忆化数组

举例验证

让我们手动验证 n=4 的情况：

f(1) = 1 // {1}
f(2) = 1 + f(1) = 1 + 1 = 2 // {2, 12}
f(3) = 1 + f(1) = 1 + 1 = 2 // {3, 13}
f(4) = 1 + f(1) + f(2) = 1 + 1 + 2 = 4 // {4, 14, 24, 124}

验证：对于4，合法数有：4, 14, 24, 124，确实为4个。

优化思路

当前的递归+记忆化解法已经足够高效，但还可以用纯递推的DP来避免递归开销：

#include<iostream>
using namespace std;

int dp[1005];

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

总结

这道题的关键在于理解递归关系和利用记忆化或动态规划来避免重复计算。通过分析问题，我们发现每个数的解可以由比它小的数的解推导出来，这是典型的DP问题特征。

掌握这种"将大问题分解为小问题"的思维方式，对于解决很多算法问题都非常有帮助。