[NOIP2001 提高组] 数的划分(剪枝)

题目描述

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

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

1,1,5
1,5,1
5,1,1

问有多少种不同的分法。

输入格式

nk （6<≤2006<n≤200，2≤≤62≤k≤6）

输出格式

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

输入输出样例

7 3

4

说明/提示

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

【题目来源】

NOIP 2001 提高组第二题

using namespace std;
const int N=1e5+10;
int a[N],res,n,k;
void prit()
{
    for(int i=1;i<k;i++) cout<<a[i]<<" ";
    cout<<a[k]<<endl;
}
void dfs(int now,int cnt)
{
    if(cnt>k||now<0) return;
    for(int i=a[cnt-1];i<=now;i++)//题目要求颠倒顺序的不算,那么就要考虑如何消除,这里就可以使用一个数组来记录上一个的值
    //如果当前不小于这个值,那么顺序就是递增的,额外提一嘴,数组此时也是储存的最小字典序的顺序;
    //这里的剪枝策略是,从不小于上一个值的位置开始,一直到现在的值
        {
            a[cnt]=i;
            if(now-i==0&&cnt==k) res++,prit();
            else dfs(now-i,cnt+1);
        }
}
int main()
{
    a[0]=1;
    cin >>n>>k;
    dfs(n,1);
    cout<<res;
    return 0;
}