NOIP2001 提高组 - 数的划分 - 算法详解与C++代码

NOIP2001 提高组 - 数的划分

题目描述

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

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

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

问有多少种不同的分法。

输入格式

'n,k' ('6<n ≤ 200'，'2 ≤ k ≤ 6')

输出格式

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

样例 #1

样例输入 #1

7 3

样例输出 #1

4

提示

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

【题目来源】

NOIP 2001 提高组第二题

算法思路

本题可以使用深度优先搜索 (DFS) 来解决。我们可以用递归函数 dfs(sum, cnt) 表示当前已经划分了 sum 的值，并且已经划分了 cnt 份。

在 dfs 函数中，我们可以枚举当前划分的值 i，并递归调用 dfs(sum + i, cnt + 1)。

当 sum 等于 n 并且 cnt 等于 k 时，表示我们已经成功地将 n 分成了 k 份，此时我们就可以更新答案 ans。

C++ 代码

#include <iostream>
using namespace std;

int n, k;
int ans = 0;

void dfs(int sum, int cnt) {
    if (sum == n && cnt == k) {
        ans++;
        return;
    }
    if (sum > n || cnt > k) {
        return;
    }
    for (int i = 1; i <= n; i++) {
        dfs(sum + i, cnt + 1);
    }
}

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

总结

本题是一道经典的组合问题，可以用 DFS 算法来解决。代码实现比较简单，但理解 DFS 算法的思想非常重要。