POJ3187---Backward Digit Sums

3500 ワード

杨辉三角の行数Nを与えて、先端の値Mと、最下層の1~Nがどのように并んでようやく先端の値Mを使うことができることを求めます.出力ディクショナリシーケンスの最小の組合せ分析:まず楊輝三角底層の各数の係数を求めて、それからDFSは答えを得ることができます
コード:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int a[15], n, cur, k, flag, vis[15], c[15][15];

void dfs() {
    if(k == n+1) {
        int res = 0;
        for(int i = 1; i <= n; i++) {
            res = res + c[n][i] * a[i];             //                
        }
        if(res == cur) {
            for(int i = 1; i < n; i++)
                printf("%d ", a[i]);
            printf("%d
"
, a[n]); flag = 1; // , , } return; } for(int i = 1; i <= n; i++) { if(flag) return; if(!vis[i]) { a[k++] = i; vis[i] = 1; dfs(); vis[i] = 0; k--; } } } int main() { scanf("%d%d", &n, &cur); memset(vis, 0, sizeof(vis)); memset(c, 0, sizeof(c)); c[0][0] = 1; for(int i = 1; i <= n; i++) // for(int j = 1; j <= i; j++) c[i][j] = c[i-1][j-1] + c[i-1][j]; k = 1; flag = 0; dfs(); return 0; }