怎么开通公众号_微信小程序生成平台系统_合肥网站推广助理_保定seo推广

题目描述

将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：n=7，k=3，下面三种分法被认为是相同的。

1,1,5;
1,5,1;
5,1,1.

问有多少种不同的分法。

输入格式

n,k （6<n≤200，2≤k≤6）

输出格式

1 个整数，即不同的分法。

输入输出样例

输入

7 3

输出

4

说明/提示

四种分法为：
1,1,5;
1,2,4;
1,3,3;
2,2,3.

【题目来源】

NOIP 2001 提高组第二题

代码：

#include <bits/stdc++.h>
using namespace std;// 全局变量：
// mySum 表示目标和 n，即需要被分割的整数。
// nn 表示分割份数 k。
// res 用于统计所有满足条件的分割方法数。
// b 用于存储当前递归过程中每一部分的取值。
int mySum;
int res = 0;
int nn;
vector<int> b;// DFS 递归函数说明：
// 参数 x：当前正在确定第 x 个部分（从 1 开始计数）。
// 参数 start：当前部分的最小取值，确保分割方案保持非递减（避免重复计数）。
// 参数 sum：到目前为止已选数字的累加和。
void dfs(int x, int start, int sum) {// 如果当前累加和超过目标值，直接剪枝，返回if(sum > mySum)return;// 当 x 超过 nn 时，说明所有 k 个部分都已被确定if(x > nn) {// 如果当前累加和正好等于目标值，说明找到了一种有效分割方法if(sum == mySum) {int index = 1; // 此变量没有实际作用，仅作占位res++;       // 有效分割方法计数器加1}return;}// 枚举当前部分可能取的值，从 start 开始取，保证非递减顺序// 剪枝条件：即使后续所有部分均取当前值 i，也不会使总和超过 mySumfor(int i = start; sum + (nn - x + 1) * i <= mySum; i++) {b[x] = i;           // 将第 x 部分的值设为 i// 递归调用 dfs，为下一部分确定取值// 参数解释：x+1 表示处理下一部分，i 作为新的最小值（保证非递减），sum + i 为新的累加和dfs(x + 1, i, i + sum);}
}int main()
{// 输入目标整数 mySum 和分割份数 nncin >> mySum >> nn;// 初始化 vector b，大小为 nn+1（从下标 1 开始使用），初始值设为 1b.assign(nn + 1, 1);// 从第 1 部分开始递归，初始最小值为 1，累加和从 0 开始dfs(1, 1, 0);// 输出满足条件的不同分割方法的数量cout << res;return 0;
}

详细步骤分析

1. 问题背景与要求
   本题要求将一个整数 n 分成 k 份，每份至少为 1，并且忽略不同排列顺序（即 1,1,5 与 1,5,1 等视为同一种方案）。例如，对于 n=7, k=3，有 4 种不同分法：
   • 1,1,5
   • 1,2,4
   • 1,3,3
   • 2,2,3
2. 全局变量定义
   • mySum 保存目标整数 n。
   • nn 表示分割份数 k。
   • res 用于统计所有合法分法的数量。
   • b 数组用于存储当前 DFS 过程中每一部分的具体取值（从下标 1 开始使用）。
3. DFS 函数的设计思想
   • 递归参数：
     • 参数 x 表示当前正在确定第 x 个部分。
     • 参数 start 确保当前部分的取值不小于前一个部分的取值，从而使得整个分割方案呈非递减序列，避免重复计数。这里for循环从start开始，保证后面的数字是大于等于前面的，从而形成了升序序列
     • 参数 sum 表示当前已经选定的各部分的累加和。
   • 终止条件：
     • 如果 sum > mySum，则当前分支不可能得到合法答案，直接返回。
     • 当 x > nn 时，说明所有 k 个部分均已确定，此时如果 sum == mySum，说明找到了一种合法的分法，将计数器 res 加 1。
   • 递归搜索与剪枝：
     • 在 for 循环中，枚举当前部分可能的取值 i，起始值为 start。
     • 循环条件 sum + (nn - x + 1) * i <= mySum 保证即使剩下的所有部分都取最小值 i，累加和也不会超过目标 mySum。这一步是有效的剪枝，避免无效的递归分支。
     • 每次递归调用时，将当前部分赋值为 i，并更新累加和为 sum + i，同时传入新的最小取值 i 保持顺序不变。
4. 主函数中的流程
   • 首先读取输入的目标整数 mySum 和分割份数 nn。
   • 使用 b.assign(nn + 1, 1) 初始化数组 b。
   • 调用 dfs(1, 1, 0) 开始递归搜索，从第 1 个部分开始，最小取值为 1，初始累加和为 0。
   • 最后输出变量 res 的值，即所有满足条件的分割方法数目。