信息学奥赛一本通T1440-数的划分,思路清晰暴力！

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 全局变量声明
int n, k, jjj = 0; // n: 目标和，k: 最大分割数，jjj: 计数器
int a[105]; // 存储当前分割方案的数组
void dfs(int x, int y, int z) {
    // 如果当前分割层数超过最大分割数
    if (x > k) {
        // 如果当前分割的和等于目标和
        if (z == n) {
            jjj++; // 计数器加一
        }
        return; // 返回上一层递归
    }
    // 遍历从y到n-z的所有可能值
    for (int i = y; i <= n - z; i++) {//一定要n-z，不然太暴力了会超时(做人不能太暴力哦)
        a[x] = i; // 将当前值存入数组
        dfs(x + 1, i, z + i); // 递归调用下一层,y=i防止相同分割
    }
}
int main() {
    cin >> n >> k; // 输入目标和和最大分割数
    dfs(1, 1, 0); // 调用深度优先搜索函数，初始参数为1, 1, 0
    cout << jjj << endl; // 输出满足条件的分割方案数量
    return 0;
}