P1118 [USACO06FEB] Backward Digit Sums G/S

题目描述

FJ 和他的奶牛们喜欢玩一个心算游戏。他们将数字从 到 按某种顺序写下来，然后将相邻的数字相加，得到一个数字更少的新列表。他们重复这个过程，直到只剩下一个数字。例如，游戏的一种情况（当 时）可能是这样的：

    3   1   2   4
      4   3   6
        7   9
         16

在 FJ 背后，奶牛们开始玩一个更难的游戏，她们试图从最终的总和和数字 中确定起始序列。不幸的是，这个游戏有点超出了 FJ 的心算能力。

编写一个程序来帮助 FJ 玩这个游戏，并跟上奶牛们的步伐。

输入格式

共一行两个正整数 。

输出格式

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

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

输入输出样例 #1

输入 #1

4 16

输出 #1

3 1 2 4

说明/提示

• 对于 的数据，；
• 对于 的数据，；
• 对于 的数据，，。 （由 ChatGPT 4o 翻译）

首先，观察起始序列和sum的关系，我们可以先举几个例子

可以发现，系数符合杨辉三角。且序列里1~n每个数字只出现一次。 那可以类比八皇后问题，其剪枝条件就是前几项的和已经大于sum。

cpp代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<unordered_map>
using namespace std;

int readint(){	//快速读入 
	char ch=getchar();
	int x=0;
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x;
}
int ans[14]={};
int visited[14]={};
int n,sum;
int a[14]={};
void init(){
	a[0]=a[n-1]=1;
	for(int i=1;i*2<=n;i++){
		a[i]=a[n-i-1]=(n-i)*a[i-1]/i;
	}
}
int f(int i,int num,int v){
	if(v>sum){	//大于sum，则后几项无比要再加入。
		return 0;
	}
	if(i==n){
		if(v==sum){
            ans[i]=num;
             return 1;
        }
		else return 0;
	}
	visited[num]=1;
	for(int j=1;j<=n;j++){
		if(!visited[j] && f(i+1,j,v+j*a[i])){
			ans[i]=num;
			return 1;
		};
	}
	visited[num]=0;
	return 0;
}
int main(){
	n=readint();sum=readint();
    init();
    if(f(0,0,0)) for(int i=1;i<=n;i++) printf("%d ",ans[i]);
	return 0;
}