P1118 [USACO06FEB] Backward Digit Sums G/S

原题

Description

FJ and his cows enjoy playing a mental game. They write down the numbers from 1 toN(1≤N≤10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N=4) might go like this:

    3   1   2   4
      4   3   6
        7   9
         16

C++

Behind FJ’s back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number NN. Unfortunately, the game is a bit above FJ’s mental arithmetic capabilities.

Write a program to help FJ play the game and keep up with the cows.

Input

共一行两个正整数 n,sum。

Output

输出包括一行，为字典序最小的那个答案。

当无解的时候，请什么也不输出。

Sample 1

4 16

3 1 2 4

Hint

• 对于 40% 的数据，1≤n≤7；
• 对于 80% 的数据，1≤n≤10；
• 对于100% 的数据，1≤n≤12,1≤sum≤12345。

解题思路

杨辉三角+dfs+剪枝

不妨把杨辉三角的写出来，就会发现每一项对应答案前的系数，之后就是普通dfs。

要注意的是每次都计算的话时间会超，所以我们把前几项的和加一起判断它是否大于sum,大于的话就没必要继续下去，这样就可以节省很多时间。

AC代码

#include <iostream>
#include <queue>
using namespace std;
int a[15],b[15][15];
int n,sum;
bool vis[15];
void dfs(int k,int sum1){
	if(sum1>sum) return ;    //剪枝
	if(k>n){
		if(sum1==sum) {
			for(int i=1;i<=n;i++)
			printf("%d ",a[i]);
			exit(0);
		}
	}
	
	for(int i=1;i<=n;i++){
		if(vis[i]==0) {
			a[k]=i;
			vis[i]=1;
			dfs(k+1,sum1+i*b[n][k]);
			vis[i]=0;
		} 
	}
}
int main(){
	cin>>n>>sum;
    //系数 杨辉三角
	b[1][1]=1;
	for(int i=2;i<=n;i++)
		for(int j=1;j<=i;j++){
			b[i][j]=b[i-1][j]+b[i-1][j-1];
		}
	dfs(1,0); 
	return 0;
}