搜索剪枝题

手摸几个样例，便能发现：若最开始的 $n$ 个数分别为 $a_1, a_2,a_3 ,…，a_n$ ，则最下面的那个数为：

就是系数为杨辉三角的第 $n$ 行

考虑dfs，若没有剪枝是 $O(n!)$ ，只能得30pts

考虑剪枝：

若你选择了前几个数，那么它可能表示出的数的上下界就能确定，只需看 $s$ 在不在这个范围内即可

我确定上下界的方法是当dfs已经确定了前一半的数后，后面剩余的数若升序排，一定是下界；若降序，为上界， 这是因为 $C_{n}^{i}$ 在一半以后是单调递减的。

就有一个并非最有但是代码好写的代码：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int C[20][20]={{0},{0,1},{0,1,1},{0,1,2,1},{0,1,3,3,1},{0,1,4,6,4,1},{0,1,5,10,10,5,1},{0,1,6,15,20,15,6,1},{0,1,7,21,35,35,21,7,1},{0,1,8,28,56,70,56,28,8,1},{0,1,9,36,84,126,126,84,36,9,1},{0,1,10,45,120,210,252,210,120,45,10,1},{0,1,11,55,165,330,462,462,330,165,55,11,1},{0,1,12,66,220,495,792,924,792,495,220,66,12,1},{0,1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1},{0,1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1},{0,1,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1}};
//表
int n,s,a[20],b[20];

//剪枝方案：当排完前一半时，以后每次都计算上下界，若不符，return 

bool flag;
int vis[20];

void dfs1(int x){//wahning最爱的暴力代码
	if (flag) return;
	if (x==n+1){
		int res=0;
		for (int i=1;i<=n;i++) res+=a[i]*C[n][i];
		if (res==s){
			for (int i=1;i<=n;i++) printf("%d ",a[i]);
			flag=1;
		}
		return;
	}
	for (int i=1;i<=n;i++){
		if (!vis[i]){
			vis[i]=1;
			a[x]=i;
			dfs1(x+1); 
			vis[i]=0;
		}
	}
}

bool cmp(int x,int y){
	return x>y;
}
bool check(int x){
	int minn=0,maxx=0;
	for (int i=1;i<=x-1;i++){
		minn+=a[i]*C[n][i];
	}
	maxx=minn;
	
	int top=x-1;
	for (int i=1;i<=n;i++){
		if (!vis[i]){
			b[++top]=i;
		}
	}
	for (int i=x;i<=n;i++){
		minn+=b[i]*C[n][i];
	}
	sort(b+x,b+n+1,cmp);
	for (int i=x;i<=n;i++){
		maxx+=b[i]*C[n][i];
	}
	if (minn<=s && s<=maxx) {
		return 1;
	}
	else return 0;
}

void dfs(int x){
	if (flag) return;
	if (x==n+1){
		int res=0;
		for (int i=1;i<=n;i++){
			res+=a[i]*C[n][i];
		}
		if (res==s){
			for (int i=1;i<=n;i++){
				printf("%d ",a[i]);
			}
			printf("\n");
			flag=1;
		}
		return;
	}
	if (x>n/2){
		if (!check(x)){
			return;
			
		}
	}
	for (int i=1;i<=n;i++){
		if (!vis[i]){
			vis[i]=1;
			a[x]=i;
			dfs(x+1);
			vis[i]=0;
		}
	}
}

int main(){
	scanf("%d%d",&n,&s);
	if (n<=8){//wahning最爱的暴力分
		dfs1(1);
		return 0;
	}
	dfs(1);
	return 0;
}