【组合问题】-数的划分

[NOIP2001 提高组] 数的划分 - 洛谷


解题思路:

(1)分析题意,本题为组合问题,将n分成k份,并且每一份都不为空,说明这k份中没有0,而且重复的数字是可以多次使用的,比如7分成3分1,1,5,其中1出现了两次,说明可行性条件并不需要标记数字是否使用过

(2)那么再来想想,可行性条件到底是什么呢?1,1,5和5,1,1是同一种方案,那么是不是在从1开始枚举的时候,就应该把所有会出现的数字都遍历一遍呢?这样的话,到了5的时候,就不用再去判断5,1,1,实现了去重的效果。

(3)因为每个数字是可以重复使用的,所以可行性条件是i>=ans【x-1】

(4)再来考虑出口的问题,同以前的排列组合问题相同,当取够k个数的时候,即为出口,当出口完毕以后,需要判断的应该是取到的这几个数的和是否为n,如果是,计数器加1


代码实现:(40分)

#include<bits/stdc++.h>
using namespace std;
int n,m,sum,temp;
int ans[210];//ans数组存放组合的方案

void dfs(int x)
{
	if(x>m)//当取够的数字为m的时候,结束递归 
	{
		sum=0;//累加器为0 
		for(int i=1;i<=m;i++)//依次累加数字对应具体的值 
		{
			sum=sum+ans[i];
		}
		
		if(sum==n)//如果和等于n 
		temp++;//计数器增加 
		
		return;
	}
	
	for(int i=1;i<=n;i++)//依次枚举可取的数字 
	{
		if(i>=ans[x-1])//当这个数字没有用过并且大于等于前一位数字的时候可用 
		{
			ans[x]=i;//将数字存放到ans数组中  
			dfs(x+1);//继续递归 
		}
	}
}
int main()
{
	cin>>n>>m;
	dfs(1);
	cout<<temp; //输出数量 
	return 0;
} 

优化思路(60分): 

以上代码只有40分,因为数字n最大为200,那么当n大的时候,嵌套了200层循环,时间复杂度很高,所以导致了超时,该如何优化呢?

(1)如果想要分法不重复的话,那么依次升序搜索即可,如果数字可以重复的话,下一个数总是不小于前一个数的

(2)举例 7,3,将7分成3份,那么方案的第一个数字取到7/3即可,因为第一个数字一旦超过2,方案数为3,3,1,已经和1,3,3重合了,那么第一层的循环没有必要枚举到n/k以后。或者可以这么理解,将n分成k份,若想不重复,第一个数不能超过n/k,不然方案数就会重复

(3)那么我们将方案的第一个数字已经可以缩小了,稍微降低一点时间复杂度


     

#include<bits/stdc++.h>
using namespace std;
int n,m,sum,temp;
int ans[210];//ans数组存放组合的方案

void dfs(int x)
{
	if(x>m)//当取够的数字为m的时候,结束递归 
	{
		sum=0;//累加器为0 
		for(int i=1;i<=m;i++)//依次累加数字对应具体的值 
		{
			sum=sum+ans[i];
		}
		
		if(sum==n)//如果和等于n 
		temp++;//计数器增加 
		
		return;
	}
	
	for(int i=1;i<=n;i++)//依次枚举可取的数字 
	{
		if(i>=ans[x-1])//当这个数字没有用过并且大于等于前一位数字的时候可用 
		{
			ans[x]=i;//将数字存放到ans数组中  
			dfs(x+1);//继续递归 
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n/m;i++)//第一个数字取到n/m即可 
	{
		ans[1]=i;
		dfs(2);//递归深搜第二个数字 
	}
	cout<<temp; //输出数量 
	return 0;
} 

终极优化(100分):

(1)上述只对第一层进行了剪枝,其实每层循环都有一些不必要枚举的数字,同样可以剪枝,比如当n=7,k=3的时候,枚举前两个数为1,1第三个数是5的时候,正好满足1+1+5=7,此时不用再判断第三个数字为6,因为数字越来越大,绝对会超过n,那么该如何构造函数呢?

(2)dfs(1,0,1)第一个参数为开始遍历的数字,从1开始枚举,第二个参数为累加器的和,sum=0,第三个参数为取的份数,现在取第一份

(3)递归的出口变成了当取的份数超过了k份的时候,就结束,然后判断累加器里是不是为n,如果是,那么此方案可行

 (4)如何设置可行性条件呢?这里使用了利用第一个参数代替了可行性方案,因为数字是可以重复取的,但是方案数不能重复,那么取后一个数字,不能小于前一个数字,并且该数字加上此时累加器的和不能超过n,如果超过了,也就没有必要去枚举。

 (5)然后将此时的i传入到下一个递归函数中,意思是下一层的for循环,直接从这个数字开始枚举,到n-sum结束,体会这里的sum+i,就是将本层的数字放到累加器中的意思,cnt+1表示再取下一份。

#include<bits/stdc++.h>
using namespace std;
int n,k,num;

//start为下一次递归的for循环的起点,sum为取k个数的累加器,cnt表示取的个数 
void dfs(int start,int sum,int cnt)
{
	if(cnt>k)//当取的个数大于k的时候,结束递归 
	{
		if(sum==n)//如果累加器和n相等,说明这k个数拼成了n 
		num++;//计数器加1
		 
		return ;
	}
	
	for(int i=start;i<=n-sum;i++)//剪枝枚举,i枚举到n-sum即可,超过了n枚举也没有意义 
	{
		dfs(i,sum+i,cnt+1);//将此时的i和累加器还有取的份数下一次递归 
	}
}

int main()
{
	cin>>n>>k;
	dfs(1,0,1);
	
	cout<<num;
	return 0;
}


版权声明:本文为weixin_60869516原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。