\(0.\) 写在前面
这题可以有两种写法：（至少两种）
- 深搜
- 计数 \(\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}\)
标签：...,le,int,题解,枚举,long,划分,text From： https://www.cnblogs.com/DreamerX/p/cutnum-solving.html