P1832 A+B Problem（再升级）

记录110

#include<bits/stdc++.h> using namespace std; long long dp[1010];//注意longlong bool f(int x){//判断素数 if(x<2) return false; for(int i=2;i*i<=x;i++){ if(x%i==0) return false; } return true; } int main(){//完全背包 int n; cin>>n; dp[0]=1;//dp起点 for(int i=2;i<=n;i++){//遍历数字 if(f(i)){//判断素数i for(int j=i;j<=n;j++) dp[j]+=dp[j-i];//用素数i来组成数字j } } cout<<dp[n];//输出 return 0;//结束程序 }

题目传送门https://www.luogu.com.cn/problem/P1832

突破口

给定一个正整数 n，求将其分解成若干个素数之和的方案总数。

🔍 一、题目核心理解

🎯 问题描述

给定一个正整数n，求将 n 表示为若干个素数之和的方案总数。

✅ 注意：

• 顺序不同视为同一种方案（例如2+5和5+2算一种）
• 允许重复使用同一个素数（如2+2+3是合法的）
• 每个加数必须是素数

这实际上是一个“用素数作为物品，组成总和为 n 的方案数”的问题。

📌 样例解析

输入 #1：n = 7

合法分解（不考虑顺序）：

1. 7
2. 2 + 5
3. 2 + 2 + 3

共 3 种 → 输出3✅

输入 #2：n = 20→ 输出26（无需手动验证）

🧠 二、解题思路：完全背包计数模型

关键观察

• 素数可以重复使用（如两个 2）
• 方案不考虑顺序（即组合而非排列）
• 这正是完全背包的“组合类计数”问题

💡 对比：

• 如果考虑顺序（如2+5和5+2不同），则是“排列型”，需外层遍历容量
• 本题要求无序组合→ 应外层遍历物品（素数），内层遍历容量

动态规划设计

• dp[j]：表示组成数字 j 的方案总数
• 初始化：dp[0] = 1（空和，1 种方案）
• 对每个素数p（从小到大枚举）：
  • 对j = p to n：
    • dp[j] += dp[j - p]

✅ 这样能保证：每种组合只按素数递增顺序生成一次，避免重复计数

分析代码

#include<bits/stdc++.h> using namespace std; long long dp[1010]; // dp[j]：组成 j 的方案数，注意可能很大，用 long long

• n ≤ 1000，但方案数可能指数级增长（如 n=1000 时方案数极大）
• 所以用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

✅ 为什么这样不会重复计数？

• 因为我们按素数从小到大依次加入
• 所有方案都以“非递减素数序列”形式生成
• 例如：2+2+3会被生成，但3+2+2不会（因为 3 在 2 之后才被考虑）

cout << dp[n]; // 输出组成 n 的方案总数 return 0; }

⚠️ 关键细节说明

📊 补充：为什么这是“完全背包”？

本题中，每个素数可用任意多次（如多个 2），所以是完全背包。

总结：问题与解法对应