传送锚点：https://www.luogu.com.cn/problem/P1025

题目描述

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

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

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

问有多少种不同的分法。

输入格式

$n,k$ （$6<n \le 200$，$2 \le k \le 6$）

输出格式

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

样例 #1

样例输入 #1

7 3

样例输出 #1

4

提示

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

思路

这题我们在for循环时还要在进行类似于剪枝优化，如果当前的和 + 剩下的几位数乘i大于n，剪掉就完事，即代码for (int i = start; sum + i * (k - x + 1) <= n; i++)中的sum + i * (k - x + 1) <= n。

code

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 205;
int n,k;
int res = 0;//存储方案数
void dfs(int x,int start,int sum) {//x代表当前数字,start代表遍历到第几位
    if (x > k) {
        if(sum == n){
            res ++;
        }
        return;
    }
    for (int i = start; sum + i * (k - x + 1) <= n; i++) {//进行进一步剪枝优化 
     //k - x  + 1为还要填的数字个数, 
            dfs(x+1, i,sum + i);
    }

}
int main()
{
    cin >> n >> k;
    dfs(1, 1, 0);
    cout << res; 
    return 0;
}