题解 P1118 【[USACO06FEB]数字三角形Backward Digit Su…】

· · 题解

include<iostream>

include<cmath>

using namespace std; int n,sum; int a[10002];//存答案 int c[100002];//标记这个数是否被找到 int cs[13][13];//杨辉三角 int dfs(int step,int v) { //step：当前到第几个数 //v：当前的总值 //返回1找到，返回2没找到 if(v>sum) { return 0; //判断当前的值是否大于sum //如果大于就跳出，没找到 } if(step==1+n) { if(v==sum) { for(int i=1; i<=n; i++) { cout<<a[i]<<" "; } return 1;//找到 } else return 0;//没找到 } for(int i=1; i<=n; i++) { if(c[i]==0) { a[step]=i; c[i]=1;//标记 v+=a[step]cs[n][step]; //将这个数乘对应的系数 if(dfs(step+1,v)) return 1; v-=a[step]cs[n][step]; c[i]=0; //以上两行回溯 } } return 0;//到这里没找到，跳出 } int main() { cin>>n>>sum; cs[1][1]=1; cs[2][1]=1; cs[2][2]=1; //以上三行用来初始化杨辉三角的上面几层 for(int i=3; i<=n; i++) for(int j=1; j<=n; j++) { cs[i][j]=cs[i-1][j-1]+cs[i-1][j]; //计算杨辉三角对应项的系数（二项式定理） } dfs(1,0); //从第一个开始找，初始值为0 return 0; } //2-a+b //3-a+2b+c //4-a+3b+3c+d //5-a+4b+6c+4d+e //6-a+5b+10c+10d+5e+f //7-a+6b+15c+20d