P1118 数字三角形（技巧）

2019-11-11 05:04:07

字体：大中小

来源：转载

供稿：网友

题见洛谷带有技巧的搜索，用到杨辉三角形

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

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<vector>using namespace std;int n,sum,a[124];int yh[20][20];bool f[20]; void dfs(int k,int tot){ //if(tot>sum) return; if(k==n+1){ if(tot==sum){ for(int i=1;i<=n;i++) PRintf("%d ",a[i]); exit(0); } return; } for(int i=1;i<=n;i++){ if(tot+i*yh[n][k]<=sum) if(!f[i]){ a[k]=i;f[i]=true; dfs(k+1,tot+i*yh[n][k]); a[k]=0;f[i]=false;//回溯！ } }}int main(){ scanf("%d%d",&n,&sum); yh[1][1]=1; for(int i=2;i<=n;i++) for(int j=1;j<=i;j++) yh[i][j]=yh[i-1][j-1]+yh[i-1][j]; /*for(int i=1;i<=n;i++){ printf("%d ",yh[n][i]); }*/ dfs(1,0); return 0;}

上一篇：文章标题

下一篇：ZCMU-Problem E - Ones