[NOIP2001 提高组] 数的划分
题目描述
将整数 n n n 分成 k k k 份,且每份不能为空,任意两个方案不相同(不考虑顺序)。
例如: n = 7 n=7 n=7, k = 3 k=3 k=3,下面三种分法被认为是相同的。
1 , 1 , 5 1,1,5 1,1,5; 1 , 5 , 1 1,5,1 1,5,1; 5 , 1 , 1 5,1,1 5,1,1.
问有多少种不同的分法。
输入格式
n , k n,k n,k ( 6 < n ≤ 200 6<n \le 200 6<n≤200, 2 ≤ k ≤ 6 2 \le k \le 6 2≤k≤6)
输出格式
1 1 1 个整数,即不同的分法。
样例 #1
样例输入 #1
7 3
样例输出 #1
4
提示
四种分法为: 1 , 1 , 5 1,1,5 1,1,5; 1 , 2 , 4 1,2,4 1,2,4; 1 , 3 , 3 1,3,3 1,3,3; 2 , 2 , 3 2,2,3 2,2,3.
【题目来源】
NOIP 2001 提高组第二题
这道题让我很快想起来寒假集训学过的dfs和bfs。(好吧我印象最深学的最好的也就dfs了)设置三个节点,只要三个数加起来等于n就ans++(挠头,就那个感觉)
#include <iostream>
using namespace std;
int n, k,ans;
这段代码是一个递归函数,用于计算给定数字n和数字个数k的情况下,所有数字之和为n的所有可能性个数。
其中的参数解释如下:
- pre:表示上一次递归选择的数字,用于避免重复计算。
- sum:表示当前已经选择的数字之和。
- cnt:表示当前已经选择了的数字个数。
函数逻辑如下:
- 如果已选择的数字个数等于k,并且数字之和等于n,说明找到了一种可能性,ans加1。
- 对于每个可能的数字i,从上一次选择的数字开始,循环计算选择i之后的所有情况,递归调用dfs函数。
这段代码通过递归的方式遍历了所有可能的情况,并统计符合要求的情况个数。
void dfs(int pre,int sum,int cnt)
{
if (cnt == k){
if (sum == n){
ans++;
}
return;
}
for (int i = pre; sum + i * (k - cnt)<=n; i++)
{
dfs(i, sum + i, cnt + 1);
}
}
int main()
{
cin >> n >> k;
dfs(1, 0, 0);
cout << ans << endl;
return 0;
}
``