Hypercube路徑

main.cpp

#include <bits/stdc++.h>

using namespace std;

void solve(int n)
{
    int dp[1 << n];
    memset(dp, 0, sizeof(dp));

    int w[1 << n];
    for (int i = 0; i < (1 << n); i++)
        scanf("%d", &w[i]);

    queue<int> q;
    q.push(0);
    dp[0] = w[0];
    while (q.size() > 0) {
        int cur = q.front();
        q.pop();

        for (int i = 0; i < n; i++) {
            int nxt = cur ^ (1 << i);
            // to avoid going backwards
            // we only change 0 to 1
            // so the next move for n = 1, node 01
            // only 11 is valid, 00 is not considered
            if (((cur >> i) & 1) == 0 && dp[nxt] < dp[cur] + w[nxt]) {
                dp[nxt] = dp[cur] + w[nxt];
                q.push(nxt);
            }
        }
    }

    printf("%d\n", dp[(1 << n) - 1]);
}

int main()
{
    int n;
    while (scanf("%d", &n) == 1 && n)
        solve(n);

    return 0;
}