[NOIP2001 提高组] 数的划分

题目描述

将整数 $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$.

【题目来源】

NOIP 2001 提高组第二题

算法1

(dfs)

1.每一次搜索的时候从上一次搜索所选的数开始往后选 - 满足不降原则

2.进行下一次搜索的 n 减去上一次搜索中选中的数

3.n可以设为局部变量，可以减少回溯操作

4.当划分次数 = k ,判断一下剩下数是否大于上一次选中的数，如果大于则说明有合法方案 ，ans++;

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int ans,k;

void dfs(int n,int cnt,int last){

    if(cnt==k&&n>=last) {   //划分次数到位，并且当前剩余的 n 大于上一次划分的数  
        ans++;              
        return;
    }
    if(cnt==k) return;  //如果剩余的 n 小于上一次划分的数，无解

    for(int i=last; i<n; i++){   //不降原则 
        dfs(n-i,cnt+1,i);
    } 
}
int main(){

    int n;    //设为局部变量可以减少回溯 

    scanf("%d%d",&n,&k);

    dfs(n,1,1);   //至少要划分 1次

    printf("%d",ans);

    return 0;
}