luoguP1118 [USACO06FEB]数字三角形`Backward Digit Su`… 题解

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,sum;
 6 int ans;
 7 bool dis[12];
 8 int f[13][13];
 9 void shuchu() {
10     for(int i=1; i<=n; i++)
11         cout<<f[1][i]<<" ";
12 }
13 void check() {
14     for(int i=2; i<=n; i++)
15         for(int j=1; j<=n-i+1; j++)
16             f[i][j]=f[i-1][j]+f[i-1][j+1];
17         /*    for(int i=1;i<=n;i++){
18                 for(int j=1;j<=n-i+1;j++)
19                 cout<<f[i][j]<<" ";
20                 cout<<‘\n‘;
21             }*/
22 //            cout<<f[n][1]<<" ";
23     if(f[n][1]==sum) {
24         shuchu();
25         ans++;
26     }
27 }
28 void pai(int k) {
29     if(k>n&&!ans) {
30         check();
31         return;
32     }
33     for(int i=1; i<=n; i++) {
34         if(!dis[i]) {
35             dis[i]=true;
36             f[1][k]=i;
37             pai(k+1);
38             dis[i]=false;
39         }
40     }
41 }
42 inline int read() {
43     int s=0,w=1;
44     char ch=getchar();
45     while(ch<‘0‘||ch>‘9‘) {
46         if(ch==‘-‘)w=-1;
47         ch=getchar();
48     }
49     while(ch>=‘0‘&&ch<=‘9‘)
50         s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
51     return s*w;
52 }
53 int main() {
54     n=read(),sum=read();
55     pai(1);
56     return 0;
57 }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,sum;
 6 int ha[13],flag,yh[13][13];
 7 bool v[13];
 8 void print(){
 9     for(int i=1;i<=n;i++)
10         printf("%d ",ha[i]);
11 }
12 //那个函数被我删了
13 void dfs(int step,int ans){
14     if(ans>sum||flag)return;
15     if(step==n+1&&ans==sum){
16         print();
17         flag=1;//标记
18         return;
19     }
20     for(int i=1;i<=n;i++)
21         if(!v[i]){
22             ha[step]=i;
23             v[i]=true;
24             dfs(step+1,ans+i*yh[n][step]);//看顶楼的解释
25             v[i]=false;//回溯
26         }
27 }
28 
29 int main(){
30     scanf("%d%d",&n,&sum);
31     yh[1][1]=1;
32     for(int i=2;i<=n;i++)//构造杨辉三角
33         for(int j=1;j<=i;j++)
34             yh[i][j]=yh[i-1][j-1]+yh[i-1][j];
35     dfs(1,0);
36     return 0;
37 }