洛谷1118 数字三角形游戏
题目描述
有这么一个游戏：
写出一个1～N的排列a[i]，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：
3
1 2 4
4
3 6
7
9
16
最后得到16这样一个数字。
现在想要倒着玩这样一个游戏，如果知道N，知道最后得到的数字的大小sum，请你求出最初序列a[i]，为1～N的一个排列。若答案有多种可能，则输出字典序最小的那一个。
输入输出格式
输入格式：
两个正整数n，sum。
输出格式：
输出包括1行，为字典序最小的那个答案。
当无解的时候，请什么也不输出。（好奇葩啊）
输入输出样例
输入样例#1：
4 16
输出样例#1：
3 1 2 4
说明
对于40%的数据，n≤7；
对于80%的数据，n≤10；
对于100%的数据，n≤12，sum≤12345。
【思路】
Dfs+杨辉三角。
以题目数据为例：16=7+9=4+3+3+6=3+1+1+2+1+2+2+4=1*3
+ 3*1 + 3*2 + 1*4
所以可以推出公式sum=∑ Yni*Ai
状态包括深度与和，知道了公式可以剪去 和 超过sum的搜索。
【代码】
#include<iostream>
#include<cstdlib>
using namespace std; const int maxn = ; int n,M;
int A[maxn],vis[maxn];
int yn[maxn]; void get_yn() {
for(int i=;i<n;i++){
yn[i]=;
for(int j=i/;j>;j--) yn[j]=yn[i-j]=yn[j]+yn[j-];
}
}
void dfs(int d,int sum) {
if(d==n && sum==M) {
for(int i=;i<n;i++) cout<<A[i]<<" ";
exit();
}
if(sum>M) return ;
for(int i=;i<=n;i++) if(!vis[i]) {
vis[i]=;
A[d]=i;
dfs(d+,sum+yn[d]*i);
vis[i]=;
}
} int main() {
ios::sync_with_stdio(false);
cin>>n>>M;
get_yn();
dfs(,);
return ;
}