（可行性剪枝，上下界剪枝）「一本通 1.3 例 1」数的划分

「一本通 1.3 例 1」数的划分上下界剪枝做法

题目描述

将整数 \(n\) 分成 \(m\) 份，且每份不能为空，问有多少种不同的分法。

思路

• 写题解的原因就是本题并不是一个简单的搜索，而是一个可行性剪枝，即“上下界剪枝”

• 将题用数学语言就是 解方程

  \[X_1+X_2+X_3+X_4.....X_m = n \]

• 因为答案没要求次序，我们定义为递增（避免重复），那么不难发现 $a[i-1] \le a[i] $ ,这就是下界

• 当求第 \(i\) 数字时，还需要拼购 \(m-i+1\) 个数字，注意是个数！那么如果这个数过于大的话，后面一定拼不起来，所以我们可以发现当前数 \(i\) 最多不能超过 \(\frac{n}{m-i+1}\) 即\(i\) 往后的平均数，就是上界

• 所以每次枚举就可一下缩小范围了，快着不只一点呐

  

Code

#include <iostream>//可行性剪枝 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

const int manx=1e6+10;
const int mamx = 1e6 + 11;
const ll mod = 2123400401301379571;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar(); int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
int n,m,a[manx],ans;
void dfs(int k){
	if(n == 0) return;//下一步的操作让n不可能为零，所以n为零就是证明取数过大，需要返回
	if(k == m){
		if(n >= a[k - 1]) ans++;//第m次填数时如果剩下的数满足下界条件，即a[i-1]<= a[i],那就直接记录答案中
		return;
	}
	for(int i = a[k-1];i <= n/(m - k + 1); i++)// k 的 下界 和 上界 
	{
		a[k] = i;
		n -= i;
		dfs(k+1);
		n += i; 
	}
}
int main(){
	n = read();
	m = read();
	a[0] = 1;//边界
	dfs(1);
	cout<<ans<<endl;
	return 0;
}