题解0005：数的划分（洛谷P1025）

题目描述：将整数 n 分成 k 份，每份不能为空，颠倒顺序的被看成一种分法。

题目链接：https://www.luogu.com.cn/problem/P1025

题目思路：深搜剪枝，规定搜索的下一个数的范围，保证代码不会超时。

代码

#include
using namespace std;
int n,k,we=0,q=0,w;
void dfs(int a,int b){
	if(a==1){//如果搜到最后一个数 
		if(n-q>=b){//如果最后一个数>=前一个数，证明不是逆序，找对了 
			we++;//结果++ 
		} 
		return;
	}
	for(int i=b;i<=n/2;i++){//剪枝，后一个数不能大于前一个数 
		q+=i;//前面的数加起来 
		dfs(a-1,i);//递归 
		q-=i;//回溯 
	}
}
int main(){
	cin>>n>>k;
	dfs(k,1);//进入深搜 
	cout<