LightOJ - 1119 Pimp My Ride(状态压缩)

题目大意：给你N个工作，给出每个工作所需要的付出和在完成该工作之前，如果完成了其他工作所需要的额外付出，问如何做完所有工作，才能使付出达到最小

解题思路：只有14个，直接状态压缩，接着就是转移了

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 20;
const int S = (1 << 14) + 10;
int val[N][N];
int dp[S];
int n, cas = 1;
void init() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            scanf("%d", &val[i][j]);
        }
}

void solve() {
    queue<int> Q;
    memset(dp, 0x3f, sizeof(dp));

    for (int i = 0; i < n; i++) {
        Q.push(1 << i);
        dp[1 << i] = val[i][i];
    }
    int all = (1 << n) - 1;
    while (!Q.empty()) {
        int s = Q.front(); Q.pop();
        if (s == all) continue;
        for (int i = 0; i < n; i++) {
            if (s & (1 << i)) continue;
            int tmp = val[i][i];
            for (int j = 0; j < n; j++)
                if (s & (1 << j)) tmp += val[i][j];
            if (dp[s | (1 << i)] > dp[s] + tmp) {
                dp[s | (1 << i)] = dp[s] + tmp;
                Q.push(s | (1 << i));
            }
        }
    }
    printf("Case %d: %d\n", cas++, dp[all]);

}

int main() {
    int test;
    scanf("%d", &test);
    while (test--) {
        init();
        solve();
    }
    return 0;
}