Poj 3187: Backward Digit Sums

poj3187.md

Poj 3187: Backward Digit Sums

題目

分析

原始想法：

對數列排列，每次排列計算該排列的 final sum，看可不可以等於 S。

如何計算一次排列的 final sum 會是困難點，但仔細觀察，會發現可以利用 Pascal's Triangle 解決。

final_sum = sum([C(N-1, i) * x for x in data])

AC Code

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <sstream>

using namespace std;

int C[10][10];

void solve(int N, int S) {
    vector<int> data(N);
    for (int i = 0; i < N; i++)
        data[i] = i + 1;

    do {
        int value = 0;
        for (int i = 0; i < N; i++)
            value += C[N-1][i] * data[i];

        if (value == S) {
            for (int i = 0; i < N; i++) {
                if (i != 0)
                    cout << " ";
                cout << data[i];
            }
            cout << endl;
            return;
        }
    } while (next_permutation(data.begin(), data.end()));
}

int main() {
    int N, S;
    cin >> N >> S;

    // pre-compute Pascal's Triangle
    for (int i = 0; i < N; i++) {
        C[i][0] = 1;
        C[i][N-1] = 1;
    }
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N-1; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }

    solve(N, S);

    return 0;
}