题目描述

小皮皮在 $7$ 岁生日时收到了很多巧克力盒子。她的父母只允许她拿 $N$ 个巧克力。巧克力装在多种类型的盒子中，如果一个盒子包含 $k$ 个巧克力，就称它为 $\text{type-}k$ 盒子。从 $\text{type-1}$ 到 $\text{type-}N$ 的每种盒子都有无限多个。皮皮必须正好拿 $N$ 个巧克力，且不能拆开任何盒子。任务是计算皮皮有多少种不同的方式可以做到这一点。

例如，当 $N=3$ 时，有以下 $3$ 种方式：

• 一个 $\text{type-3}$ 盒子
• 一个 $\text{type-2}$ 盒子和一个 $\text{type-1}$ 盒子
• 三个 $\text{type-1}$ 盒子

输入格式：多行，每行一个整数 $N$ $(0\le N\le 5000)$

输出格式：对于每个 $N$，输出方式数

题目分析

这个问题本质上是整数划分问题（$\text{Integer Partition}$），即求将正整数 $N$ 表示为若干个正整数之和的不同方式数，其中顺序不重要。

关键观察

1. 问题本质：将 $N$ 划分为若干个正整数的和，划分的顺序不重要
2. 无限供应：每种盒子数量无限，对应划分中每个数字可以使用多次
3. 顺序无关：$2+1$ 和 $1+2$ 被视为同一种划分方式

样例分析

• $N=3$：划分有 $3$、$2+1$、$1+1+1$，共 $3$ 种
• $N=4$：划分有 $4$、$3+1$、$2+2$、$2+1+1$、$1+1+1+1$，共 $5$ 种
• $N=5$：划分有 $5$、$4+1$、$3+2$、$3+1+1$、$2+2+1$、$2+1+1+1$、$1+1+1+1+1$，共 $7$ 种

解题思路

动态规划方法

这是一个经典的完全背包问题：

• 物品：重量为 $1,2,3,\dots ,N$ 的盒子
• 背包容量：$N$
• 目标：求恰好装满背包的方案数

状态定义

设 $dp[i]$ 表示整数 $i$ 的划分数（即方式数）。

初始状态

$dp[0]=1$，表示空划分（不选任何盒子）。

状态转移方程

对于每个可能的盒子类型 $k$（从 $1$ 到 $N$），我们考虑将其加入划分中：

$$dp[j]=dp[j]+dp[j-k]\text{for }j=k\text{ to }N$$

这个转移确保了我们按非降序生成划分，避免了重复计数。

算法步骤

1. 初始化 $dp[0]=1$，其余为 $0$
2. 对于 $k$ 从 $1$ 到 $N$：
   • 对于 $j$ 从 $k$ 到 $N$：
     • $dp[j]+=dp[j-k]$
3. 对于每个查询，输出 $dp[N]$

大数处理

由于 $N=5000$ 时的划分数非常大（有几百位），需要使用高精度运算。我们实现一个简单的 $\text{BigInt}$ 类来处理大数加法。

复杂度分析

• 时间复杂度：$O(N^2\times L)$，其中 $L$ 是大数的平均位数
• 空间复杂度：$O(N\times L)$，存储所有状态的大数值

代码实现

// Boxes of Chocolates Again
// UVa ID: 10590
// Verdict: Accepted
// Submission Date: 2025-11-10
// UVa Run Time: 0.320s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

class BigInt {
private:
    vector<int> digits;
    static const int BASE = 10000;
    static const int BASE_DIGITS = 4;
    
public:
    BigInt() : digits(1, 0) {}
    
    BigInt(long long num) {
        if (num == 0) digits.push_back(0);
        while (num > 0) {
            digits.push_back(num % BASE);
            num /= BASE;
        }
    }
    
    BigInt& operator+=(const BigInt& other) {
        int carry = 0;
        int maxSize = max(digits.size(), other.digits.size());
        
        digits.resize(maxSize, 0);
        
        for (int i = 0; i < maxSize; i++) {
            int sum = digits[i] + (i < other.digits.size() ? other.digits[i] : 0) + carry;
            digits[i] = sum % BASE;
            carry = sum / BASE;
        }
        
        if (carry > 0) {
            digits.push_back(carry);
        }
        
        return *this;
    }
    
    friend ostream& operator<<(ostream& os, const BigInt& num) {
        os << num.digits.back();
        for (int i = num.digits.size() - 2; i >= 0; i--) {
            os << setw(BASE_DIGITS) << setfill('0') << num.digits[i];
        }
        return os;
    }
};

int main() {
    const int MAX_N = 5000;
    
    vector<BigInt> dp(MAX_N + 1);
    dp[0] = BigInt(1);
    
    for (int maxNum = 1; maxNum <= MAX_N; maxNum++) {
        for (int j = maxNum; j <= MAX_N; j++) {
            dp[j] += dp[j - maxNum];
        }
    }
    
    int n;
    while (cin >> n) {
        cout << dp[n] << endl;
    }
    
    return 0;
}

总结

本题通过动态规划结合高精度运算解决了大范围的整数划分问题。关键点在于：

1. 正确识别问题为整数划分/完全背包问题
2. 使用动态规划避免重复计数
3. 实现高效的大数运算处理极大结果

算法能够正确处理 $N\le 5000$ 的所有情况，在时间和空间复杂度上都是可行的。