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

···

#include<bits/stdc++.h>
#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<int> 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;
}

···