P1118 [USACO06FEB] Backward Digit Sums G/S

提示：

n=3, n=4, n=5...试试把第一行那乱序的1到n个数从左到右编为a, b, c, d, e, f, g... 并且将整个”金字塔“中的数字都用这些字母表示（每一个值都是由上面相邻的两个值之和得到的）。

使用next_permutation()函数解决如何得到1到n的数的下一个排列方式的问题。

使用next_permutation()的时候一定要用do-while循环。

思路：

1. 找到第n行的杨辉三角数字序列
2. 对于每一个1到n的数的排列都尝试用杨辉三角序列当整式的各项系数
3. 如果该整式的值与sum的值相等：输出该对于1到n的数的排列
4. 结束程序

程序：

#include<bits/stdc++.h>
using namespace std;
int n,sum,a[15],pt[15][15];
void pascalTriangle(){
	pt[1][1]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++)
			pt[i][j]=pt[i-1][j-1]+pt[i-1][j];
	}
}
int main(){
	cin>>n>>sum;
	for(int i=1;i<=n;i++)
		a[i]=i;
	pascalTriangle();
	do{
		int ts=0;
		for(int i=1;i<=n;i++)
			ts+=(pt[n][i]*a[i]);
		if(ts==sum){
			for(int i=1;i<=n;i++) cout<<a[i]<<" ";
			return 0;
		}
	}while(next_permutation(a+1,a+1+n));
	return 0;
}