【洛谷】P1118数字三角形

题目 

原题链接

分析

最简单，当然是直接莽。深搜枚举所有全排列，每枚举一个全排列，就按照它的规则计算，直至剩下一个数，然后将判断这个数与sum是否相等，相等就输出该全排列，直接结束深搜。

首先看了一下n<=12，一般来说1s之内枚举n=12的所有全排列还是勉勉强强的，再加上额外计算。那应该妥妥的超时。

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

int num[15];
int vis[15];
int n,sum;

void dfs(int k)
{
	if(k>=n)
	{
		int copy[15];
		for(int i=0;i<n;i++)
			copy[i]=num[i];
		
		for(int i=n-1;i>=1;i--)
			for(int j=0;j<i;j++)
				copy[j]+=copy[j+1];
		if(copy[0]==sum)
		{
			for(int i=0;i<n;i++)
				printf("%d%s",num[i],i<n-1?" ":"\n");
			exit(0);
		}
		return;
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			vis[i]=1;
			num[k]=i;
			
			dfs(k+1);
			
			vis[i]=0;
		}
	}
}

int main()
{
	scanf("%d%d",&n,&sum);
	dfs(0);
	return 0;
}

 

看完题目的计算规则，总感觉跟杨辉三角有点关系。不妨手动模拟一下sum的计算。

如果n为4，那么sum是a+3b+3c+d

如果n为5，那么sum是a+4b+6c+4d+e

如果n为6，那么sum是a+5b+10c+10d+5e+f

...

然后对比一下杨辉三角。。

额，，，此时，，，像发现了新大陆

sum的各项系数与杨辉三角有关！那么主题思路就有了：

那我们就可以通过预处理n<=12杨辉三角，在dfs枚举全排列中的每一个数时就乘上这个系数

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

int num[15];
int vis[15];
int n,sum;

int yh[15][15];
void init()
{
	for(int i=1;i<=13;i++) //从1开始 
	{
		yh[i][0]=1; //从0开始 
		for(int j=1;j<i;j++)
			yh[i][j]=yh[i-1][j-1]+yh[i-1][j];
	}	
}


void dfs(int k, int ans)
{
	if(k>=n)
	{
		if(ans==sum)
		{
			for(int i=0;i<n;i++)
				printf("%d%s",num[i],i<n-1?" ":"\n");
			exit(0);
		}
		return;
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			vis[i]=1;
			num[k]=i;
			
			dfs(k+1, ans+i*yh[n][k]);
			
			vis[i]=0;
		}
	}
}

int main()
{
	init();
//	for(int i=1;i<=13;i++)
//		for(int j=0;j<i;j++)
//			printf("%d%s",yh[i][j],j<i-1?"\t":"\n");
	scanf("%d%d",&n,&sum);
	dfs(0, 0);
	return 0;
}

很遗憾。。。你并没有过。。。

这题的精髓部分已经被挖掘出来了。然而仍然没过的原因，是因为dfs不加任何剪枝地遍历了整棵树。刚开始我说了n=12时1s内枚举所有全排列是很勉强的。以下我来介绍这题的两个剪枝方式！当然我看到洛谷题解里面有更强更细的剪枝，然而我并没有看懂。。。

大剪枝

dfs中有个累加的ans，一旦这个ans>sum。那么当前这个有n个数的全排列序列没有深搜完，也没必要继续下去了，因为后面无论填充什么数，它都不可能等于sum。继续深搜只是做无用功。

小剪枝

 这个是lzh大佬告诉我的，利用杨辉三角的对称性！

以n=5说明，如果n为5，那么sum是a+4b+6c+4d+e

那么我们dfs找一个全排列序列：a, b, c, d, e

注意到上式的系数是对称的，有什么好处呢？举例说：当b=3, d=5 和 当b=5, d=3，其他数位a,c,e相同，那么计算出来的sum值是一样的

又由于要求是字典序最小的，那么必定有符合题目要求的全排列必定有以下规律：a<e 且 b<d（这里仅仅是以n=5说明）

注：代码中有个细节我已经加了注释，原因我就不说了。如果懂了这个剪枝的意思，自然就明白为什么了。

 最终代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

int num[15];
int vis[15];
int n,sum;

int yh[15][15];
void init()
{
	for(int i=1;i<=13;i++) //从1开始 
	{
		yh[i][0]=1; //从0开始 
		for(int j=1;j<i;j++)
			yh[i][j]=yh[i-1][j-1]+yh[i-1][j];
	}	
}


void dfs(int k, int ans)
{
	if(k>=n)
	{
		if(ans==sum)
		{
			for(int i=0;i<n;i++)
				printf("%d%s",num[i],i<n-1?" ":"\n");
			exit(0);
		}
		return;
	}
	
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			if(ans+i*yh[n][k]>sum)
				break;
			
			if( k>n/2 && i<num[n-1-k])
				continue; //注意这里是continue，而不是break！想想为什么？
				
			vis[i]=1;
			num[k]=i;
			dfs(k+1, ans+i*yh[n][k]);
			vis[i]=0;
		}
	}
}

int main()
{
	init();
//	for(int i=1;i<=13;i++)
//		for(int j=0;j<i;j++)
//			printf("%d%s",yh[i][j],j<i-1?"\t":"\n");
	scanf("%d%d",&n,&sum);
	dfs(0, 0);
	return 0;
}