BZOJ 1653 [Usaco2006 Feb]Backward Digit Sums

题目大意

对一个1~N的排列进行如下操作：取出所有相邻的元素，之后在新的数列插入它们的和。

如此反复进行此操作，直到最后只剩下一个元素。

现在给你操作N和最终的结果，求字典序最小的可行的排列。

$N \le 10$

$N \le 10$......我还想了半天什么DP贪心blabla……直接暴力DFS就好了

在check()的时候有一种高级方法是用杨辉三角Blabla......不是很懂于是写的暴力也过了……

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,t[56],ans[56];
bool v[10];
void check()
{
	int tmp=0,tot=n,ref=n;
	for(int i=1;i<n;++i)
	{
		for(tmp++;tmp<tot;++tmp) t[++ref]=t[tmp]+t[tmp+1];
		tot=ref;
	}
	if(t[tot]==m)
	{
		for(int i=1;i<=n;++i)
		{
			if(ans[i]>t[i])
			{
				for(int j=1;j<=n;++j) ans[j]=t[j];
				return;
			}
			if(ans[i]<t[i]) return;
		}
	}
}
void DFS(int pos)
{
	if(pos>n) {check();return;}
	for(int i=1;i<=n;++i) if(!v[i])
	{
		v[i]=true;
		t[pos]=i;
		DFS(pos+1);
		v[i]=false;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(ans,0x3f3f3f3f,sizeof ans);
	DFS(1);
	for(int i=1;i<=n;++i) printf("%d%c",ans[i],i==n?'\n':' ');
	return 0;
}