题目描述
将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。
输入输出格式
输入格式：
n，k (6<n<=200，2<=k<=6)
输出格式：
一个整数，即不同的分法。
输入输出样例
输入样例#1：
7 3
输出样例#1：
4
说明
四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;
这题其实深搜就可以很快地过，但是有一个小技巧可以大大优化时间复杂度。
那就是每层往下搜的时候，不要把每个1到n的每个数都放进去，而是从上层的数到（n-y）/（k-x+1）（剩下的数的平均数），这样到最后也不需要判断是不是所有数是否等于n。
代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define ll long long #define il inline #define db double using namespace std; il int gi() { int x=0,y=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') y=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*y; } il ll gl() { ll x=0,y=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') y=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*y; } int n,k,ans; int num; void dfs(int x,int y) { if(x==k) { ans++; return; } for(int i=num;i<=(n-y)/(k-x+1);i++) { if(y+i>n) break; num=i; dfs(x+1,y+i); } } int main() { n=gi(),k=gi(); num=1; dfs(1,0); printf("%d",ans); return 0; }