P1118 数字三角形（技巧）

题见洛谷

带有技巧的搜索，用到杨辉三角形

不难看出 第几个（k）拆的数（虽说并不是拆的），系数为杨辉三角第n行，第k列的数字

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int n,sum,a[];
int yh[][];
bool f[]; 
void dfs(int k,int tot)
{
    //if(tot>sum) return;
    if(k==n+){
        if(tot==sum){
          for(int i=;i<=n;i++)
           printf("%d ",a[i]);
          exit();
        }

        return;
    }
    for(int i=;i<=n;i++){
      if(tot+i*yh[n][k]<=sum)
       if(!f[i]){
         a[k]=i;f[i]=true;
         dfs(k+,tot+i*yh[n][k]);
         a[k]=;f[i]=false;//回溯！ 
       }
    }

}
int main()
{
    scanf("%d%d",&n,&sum);
    yh[][]=;
    for(int i=;i<=n;i++)
     for(int j=;j<=i;j++)
        yh[i][j]=yh[i-][j-]+yh[i-][j];
    /*for(int i=1;i<=n;i++){
      printf("%d ",yh[n][i]);
    }*/

    dfs(,);

    return ;
} 
           

转载于:https://www.cnblogs.com/dfsac/p/6819777.html