CODEVS 1039 数的划分

题目描述 Description

将整数n分成k份,且每份不能为空,任意两种划分方案不能相同(不考虑顺序)。
例如:n=7,k=3,下面三种划分方案被认为是相同的。
1 1 5

1 5 1

5 1 1
问有多少种不同的分法。

输入描述 Input Description

输入:n,k (6<n<=200,2<=k<=6)

输出描述 Output Description
输出:一个整数,即不同的分法。

样例输入 Sample Input

 7 3

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

 {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;}

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int f(int,int,int);
int main(){
    int n,k;
    cin>>n>>k;
    cout<<f(n,k,1);
    return 0;
}
int f(int a,int b,int c){
    int i,g=0;
    if(b==1) g=1;
        else for(i=c;i<=a/b;i++)
                     g+=f(a-i,b-1,i);
    return g;
}

 

此条目发表在CODEVS分类目录。将固定链接加入收藏夹。