杨辉三角:
//https://www.luogu.com.cn/problem/P1118 //最优性剪枝: //由高中知识可得,abcd四个数符合杨辉三角的数相乘,即 //res=a+3*b+3*c+d,前面的常数项也就是杨辉三角的数字 //根据此结论,进行剪枝 //由于暴力枚举全排列+部分剪枝不可过,所以要考虑方法性剪枝 #include<bits/stdc++.h> using namespace std; const int N=2e5+10; int cow[N],n,m,k; int res[N]; bool vis[N]; //当前搜索到第cnt个数,当前的数是num,前cnt个数的和是sum bool dfs(int cnt,int num,int sum) { if(sum>k) return false; if(cnt==n){ if(sum==k){ res[cnt]=num; return true; } return false; } vis[num]=true;//当前的数字标记,被搜过了 for(int i=1;i<=n;i++){ if(!vis[i]&&dfs(cnt+1,i,sum+cow[cnt]*i)){ //如果没被搜过并且dfs为true res[cnt]=num; return true; } } vis[num]=false;//退出标记,为先前的循环做准备 return false; } int main() { cin>>n>>k; cow[0]=cow[n-1]=1; if(n>1) for(int i=1;2*i<n;i++) cow[i]=cow[n-i-1]=(n-i)*cow[i-1]/i; //for(int i=0;i<=n;i++) cout<<cow[i]<<' '; if(dfs(0,0,0)) for(int i=1;i<=n;i++) cout<<res[i]<<' '; return 0; }