P1832 A+B Problem（再升级）

记录110#includebits/stdc.h using namespace std; long long dp[1010];//注意longlong bool f(int x){//判断素数 if(x2) return false; for(int i2;i*ix;i){ if(x%i0) return false; } return true; } int main(){//完全背包 int n; cinn; dp[0]1;//dp起点 for(int i2;in;i){//遍历数字 if(f(i)){//判断素数i for(int ji;jn;j) dp[j]dp[j-i];//用素数i来组成数字j } } coutdp[n];//输出 return 0;//结束程序 }题目传送门https://www.luogu.com.cn/problem/P1832突破口给定一个正整数 n求将其分解成若干个素数之和的方案总数。 一、题目核心理解 问题描述给定一个正整数n求将 n 表示为若干个素数之和的方案总数。✅ 注意顺序不同视为同一种方案例如25和52算一种允许重复使用同一个素数如223是合法的每个加数必须是素数这实际上是一个“用素数作为物品组成总和为 n 的方案数”的问题。 样例解析输入 #1n 7合法分解不考虑顺序72 52 2 3共 3 种 → 输出3✅输入 #2n 20→ 输出26无需手动验证 二、解题思路完全背包计数模型关键观察素数可以重复使用如两个 2方案不考虑顺序即组合而非排列这正是完全背包的“组合类计数”问题 对比如果考虑顺序如25和52不同则是“排列型”需外层遍历容量本题要求无序组合→ 应外层遍历物品素数内层遍历容量动态规划设计dp[j]表示组成数字 j 的方案总数初始化dp[0] 1空和1 种方案对每个素数p从小到大枚举对j p to ndp[j] dp[j - p]✅ 这样能保证每种组合只按素数递增顺序生成一次避免重复计数分析代码#includebits/stdc.h using namespace std; long long dp[1010]; // dp[j]组成 j 的方案数注意可能很大用 long longn ≤ 1000但方案数可能指数级增长如 n1000 时方案数极大所以用long long防止溢出题目未说取模需存大数bool f(int x){ // 判断 x 是否为素数 if(x 2) return false; for(int i 2; i * i x; i){ if(x % i 0) return false; } return true; }标准的素数判断函数x 2→ 非素数试除到√x即可int main(){ int n; cin n; dp[0] 1; // 基础情况和为 0 有 1 种方案什么都不选for(int i 2; i n; i){ // 枚举所有可能的“物品”2 到 n if(f(i)){ // 如果 i 是素数 for(int j i; j n; j) dp[j] dp[j - i]; // 完全背包用素数 i 更新 dp[j] } } 核心逻辑说明外层循环遍历所有可能的素数i从 2 到 n内层循环j i to n正序正序是完全背包的标志允许重复使用dp[j] dp[j - i]表示在已有方案基础上加入一个i✅ 为什么这样不会重复计数因为我们按素数从小到大依次加入所有方案都以“非递减素数序列”形式生成例如223会被生成但322不会因为 3 在 2 之后才被考虑cout dp[n]; // 输出组成 n 的方案总数 return 0; }⚠️ 关键细节说明细节说明dp[0] 1组合计数问题的标准起点素数判断范围只需判断2..n因为大于 n 的素数不可能用于组成 n内层正序完全背包特征允许多次使用同一素数外层素数顺序保证组合无序避免25和52被重复计算数据类型用long long防止方案数溢出n1000 时方案数可达数百万甚至更多 补充为什么这是“完全背包”背包类型物品使用次数内层循环方向0-1 背包每件最多1次倒序完全背包每件无限次正序本题中每个素数可用任意多次如多个 2所以是完全背包。总结问题与解法对应题目要求DP 设计分解为素数之和物品 所有 ≤n 的素数允许重复完全背包不考虑顺序外层遍历素数从小到大求方案总数dp[j] dp[j - p]初始化dp[0]1