洛谷 [P1118] IOI1994 数字三角形

简单dfs

我们注意到，题目中的运算方式与杨辉三角极其相似，所以说本题实际上是一道加权的杨辉三角，搜索系数

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
int init(){
    int rv=0,fh=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') fh=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        rv=(rv<<1)+(rv<<3)+c-'0';
        c=getchar();
    }
    return fh*rv;
}
int n,num,c[20][20],temp[20];
bool f[20];
void work(){
    c[1][1]=1;
    for(int i=2;i<=n;i++){
        c[i][1]=c[i][i]=1;
        for(int j=2;j<i;j++){
            c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }
}
void print(){
    for(int i=1;i<=n;i++){
        printf("%d ",temp[i]);
    }
}
void dfs(int k,int cur){
    if(cur>num) return;
    if(k==n+1){
        if(cur==num) {print();exit(0);}
        else return ;
    }
    for(int i=1;i<=n;i++){
        if(!f[i]){
            f[i]=1;
            temp[k]=i;
            dfs(k+1,cur+i*c[n][k]);
            f[i]=0;
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    n=init(),num=init();
    work();
    dfs(1,0);
    fclose(stdin);
    return 0;
}