数的划分
题目描述
将整数 \(n\) 分成 \(k\) 份，且每份不能为空，问有多少种不同的分法。当 \(n=7, k=3\) 时，下面三种分法被认为是相同的：\(1,1,5\); \(1,5,1\); \(5,1,1\).
输入格式
一行两个数 \(n\) , \(k\)。
输出格式
一行一个整数，即不同的分法数。
样例
样例输入
7 3样例输出
4样例解释
四种分法为：\(1,1,5\)；\(1,2,4\)；\(1,3,3\)；\(2,2,3\)。
数据范围与提示
\(6 \leq n \leq 200,\) \(2 \leq k \leq 6\)。
简单搜索剪枝。
每次从上次的开始搜索。然后如果没法取的比上一个大就返回。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cctype>
#define int long long
#define rep(i,a,n) for(register int i=a;i<=n;++i)
#define dwn(i,n,a) for(register int i=n;i>=a;--i)
using namespace std;
int n,k,ans;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x==0)return;
write(x/10);
putchar(x%10+'0');
}
void dfs(int rem,int last,int step)
{
if(rem==0&&step==k)
{
++ans;
return;
}
if(rem&&step>=k)return;
if(last>rem&&step<k)return;
rep(i,last,rem)
{
dfs(rem-i,i,step+1);
}
return;
}
signed main()
{
n=read(),k=read();
dfs(n,1,0);
if(ans)write(ans);
else putchar('0');
return 0;
}