P238 [NOIP2001 提高组] 数的划分

读题

将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。问有多少种不同的分法。

算法思路

读完题后，能很自然地想到这是一道 深度优先搜索 的题目。

明白了算法后，就需要考虑 搜索方法 了。

可以先定义一个 $deep$ 变量，用于标记递归到 第哪一个数 ，如果 $deep$ 大于 $k$ ，那么就终止递归；否则，循环遍历出条件范围内的数，进入下一层递归。 可以先写出如下递归函数：（其中，关于是否满足各数之和是否为 $n$ ，可以先用一个求和函数凑合一下，一会儿再优化）

int qh()
{
	int ansq=0;
	for (int i=0;i<=l;++i)
		ansq+=a[i];
	return ansq;
}
void dfs(int deep,int be)
{
	if (deep>k)
	{
		if (qh()==n)
			ans++;
		return;
	}
	for (int i=be;i<n;++i)
	{
		a[l]=i;
		l++;
		dfs(deep+1,i);
		l--;
	}
}

但是，很显然，这样的代码时间复杂度过高，交上去会有 2 个测试点超时，我们需要优化。 其中，求和函数可以不用每次都运行一遍循环，只需要在递归函数内用一个 $qh$ 变量存储之前的数字之和，每次递归时加上遍历的数就行了。如这样：

for (int i=be;i<n;++i)
{
	qh+=i;
	dfs(deep+1,i);
	qh-=i;
}

但是还是超时，我们还能从递归内的循环次数入手，尽量减少不必要的循环次数，经过简单思考，就可以发现 $i$ 的最大值可以一直到 $n-qh$ 。于是，有了下面的 AC 代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,qh,ans;
void dfs(int deep,int be)
{
	if (deep>k||qh>n) //如果qh已经大于n，就可以直接结束
	{
		if (qh==n)
			ans++;
		return;
	}
	for (int i=be;i<=n-qh;++i)
	{
		qh+=i;
		dfs(deep+1,i);
		qh-=i;
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	dfs(1,1);
	printf("%d",ans);
	return 0;
}