P1118 [USACO06FEB]Backward Digit Sums G/S 题解

一.题意

　　给出一个数n和一个目标值target，target是某序列按照杨辉三角方式叠加的数的最后一行（也可以说是第一行），求这个序列（要求字典序最小奥）。

二.切入点

　　1.怎么暴力？可以用next_permutation(老懒人了),复杂度是O(12!)，12！= 4.7e8，本题的时限是1s，最多也就1e8，显然过不了，所以需要剪枝。

　　2.怎么剪枝？首先需要明白这个总和是怎么算的，根据叠加方式，那应该是杨辉三角的第n列系数。有了计算总和的办法，就可以使用比较常见的剪枝策略，当目标累加值大于target就给它剪掉，肥肠好用哟ovo/****

三.实现过程中的难点

　　我相信，在想出预处理杨辉三角系数后，这道题应该也难不住大家了。不过作为蒟蒻，实际上调得蛮久的，因为蒟蒻的debug能力还不够厉害嘛，以后不要删掉测试输出了，不然要打好多遍，代码高效性远大于代码美观程度，当然是这样的，也算给本蒟蒻一个教训。

最后，谢谢阅读，奉上本蒟蒻的代码：\ qaq /完美收场

#include
#define rep(i,x,n) for(int i=x;i<=n;i++)

using namespace std;

int s[20][20];//系数
int st[20];//判断dfs时数有没有被枚举过
int d[20];//数字
vector q;

int n,target;

void init(int n=12)
{
	rep(i,1,n) d[i]=i;//初始化数组
	
	s[1][1]=1;
	rep(i,2,n) rep(j,1,n) s[i][j]=s[i-1][j-1]+s[i-1][j];//初始化杨辉三角系数
}

void dfs(int x,int sum)
{
	if(sum>target) return;
	if(x==n&&sum==target) 
	{
		for(auto i:q) cout << i << ' ';
		exit(0);
	}
	rep(i,1,n)
	{
		if(!st[i])
		{
			st[i]=1;
			q.push_back(i);
			dfs(x+1,i*s[n][x+1]+sum);
			q.pop_back();
			st[i]=0;
		}
	}
}

int main()
{
	init();//预处理出系数
	cin >> n >> target;
	dfs(0,0);
	return 0;
}