\(0.\) 写在前面

1.3【例题1】数的划分 - TuringEDU

P2706 数的划分 - TopsCoding

这题可以有两种写法：（至少两种）

1. 深搜
2. 计数 \(\text{DP}\)

接下来将会依次讲解

\(1.\) 深搜

轻而易举可以看出，本题转化为数学模型就是把一个大于 \(0\) 的整数 \(n\) 无序划分为 \(k\) 份的方案数

即求不定方程 \(x_1 + x_2 + x_3 + ...+ x_k = n,1 \le x_1 \le x_2 \le x_3 \le ... \le x_k\) 的解的个数

那就可以依次枚举 \(x_1 , x_2 , x_3 , ... , x_k\) 的值，再加以判断。

可是如果直接搜索的话，运行速度会很慢，所以我们要考虑剪枝。

我们发现，枚举 \(x_1 , x_2 , x_3 , ... , x_k\) 的值有以下两个多次重复的地方：上界与下界

\(1.\) 由于枚举 \(x_1 , x_2 , x_3 , ... , x_k\) 中 \(x_1 , x_2 , x_3 , ... , x_k\) 值的重复概率很大，造成大量无效操作，所以我们考虑枚举依次递增

所以设 int f[9]，该数组记录枚举的方案数，扩展第 \(i\) 个方案时的下界应是不小于前一个的值，即 \(f_{i-1} \le f_i\)

\(2.\) 假设我们将 \(n\) 已经分解为了 \(f_1,f_2,f_3...f_{i-1}\)，时，则 \(f_i\) 的最大值应保证以后的 \(f_{i+1},f_{i+2}...f_n\) 都不下降，设 \(t=n-(f_1+f_2+...+f_{i-1})\) 所以 \(f_i\) 的上界是 \(\frac{t}{k-i+1}\)（\(k\) 表示一共分成多少块，题面提到过）

所以我们就可以写出 \(\text{AC Code}\) 了：

#include<bits/stdc++.h>
#define int long long//重点：十年OI一场空，不开 long long 见祖宗（doge
using namespace std;
int ans,n,f[9]={0,1},k;//初始化f[1]=1，因为第一个数最低一定是1
inline void dfs(int p)
{
	if(n==0) return;//如果n减完了，那就不用再减了
	if(p==k)//如果累计加了k个数
	{
		if(n>=f[p]) ans++;//如果分完了，答案+1
		return;
	}
	for(int i=f[p];i<=n/(k-p+1);i++)//确定上下界
		f[p+1]=i,n-=i,dfs(p+1),n+=i;//保存状态，搜索，回溯
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0); //读入优化（然而并没有什么用）
	cin>>n>>k;
    dfs(1);//搜索，从第一个数开始
	cout<<ans;
	return 0;
} 

\(2.\) 计数 \(\text{DP}\)

由于题目中 \(6 < n \le 200,2 \le k\le 6\) 因此我们十分敏感地也可以设 \(f_{i,j}\) 表示 \(i\) 个数，来分成 \(j\) 份的方案数

我们分类讨论：

\(1. i < j\) 时，数不够分，因此无解，但题目中说了不可能 \(i<j\)，因此可以省略

\(2. i=j\) 时，刚好一种情况，够分，需要 \(f_{0,0}=1\)

\(3. i>j\) 时， 这是重点，我们考虑：

举个例子：假如现在有一个状态（\(k=3\)）：\(\{2,2,3 \}\) 这 \(3\) 个数里面不含 \(1\)，我们就可以知道这个状态可以由 \(\{1,1,2\}\) 推出来，再由 \(f_{i,j}\) 表示的含义，得 \(f_{i,j}=f_{i-j,j}+f_{i-1,j-1}\)

综合以上，再加上初始化，得 \(\text{AC Code2}\)：

//Or we can do this:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[501][501];//f开全局，可以清零
signed main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {   
        f[i][1]=1;
        f[i][0]=1;
    }//初始状态，根据常识可知：i个数选0或1个只有一种选法
    for(int i=2;i<=n;i++)
        for(int x=2;x<=k;x++)
            if(i>x)//情况3
                f[i][x]=f[i-1][x-1]+f[i-x][x];
            else//剩下情况，迭代前面的
                f[i][x]=f[i-1][x-1];
    cout<<f[n][k];//n分成k个的方案数
    return 0;
}

\(\huge\text{THE END}\)