1 条题解
-
0
【本题解由站长编写】
把 n 划分成若干个正整数之和的方案数,顺序不同算同一种。整数划分 DP 必须用完全背包(硬币交换)写法:外层枚举「份数 j」从 1 到 n,内层正序枚举「总和 i」从 j 到 n,有
dp[i] += dp[i-j]。⚠️ 循环顺序不能反——若外层枚举金额、内层枚举份数,算出来的是有序组合数(n=77 会得到 7.7×10^22 量级),而不是不区分顺序的划分。⚠️ 评测把「只有它自己」也算一种:n=77 期望 10619863,而纯 ≥2 项的划分是 10619862,恰好差 1,所以不要减 1。n≤100 时 p(100)=190569292 仍超 int32,必须用 long long。代码(C++17)
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<long long> dp(n + 1, 0); dp[0] = 1; // 完全背包写法:外层份数,内层正序枚举总额 for (int j = 1; j <= n; j++) for (int i = j; i <= n; i++) dp[i] += dp[i - j]; cout << dp[n] << endl; // 不减 1:评测把只有自身那一种也算进去 return 0; }
- 1
信息
- ID
- 4184
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者