洛谷P6883 [COCI20162017#3] Kroničan 题解 状压DP入门题

题目链接：https://www.luogu.com.cn/problem/P6883

解题思路：

对于每个状态 \(s\)，它的上一个状态 \(s'\) 必然满足：\(s'\) 的二进制表示中恰好有一位和 \(s\) 不相同，且那一位为 \(1\)。（设这一位为第 \(i\) 位）

然后遍历 \(s\) 的二进制表示中所有为 \(1\) 的那些位（设为第 \(j\) 位）。

\(i \rightarrow j\) 可以看做一个状态转移。

设 \(f_{s}\) 为到达状态 \(s\) 的最小代价总和，则 \(f_{s} = \max\{ f_{s'} + c_{i,j} \}\)

示例程序：

#include <bits/stdc++.h>
using namespace std;
int n, k, c[22][22], f[1<<20], ans = (1<<29);
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            cin >> c[i][j];
    memset(f, 0x3f, sizeof(f));
    f[(1<<n)-1] = 0;
    for (int st = (1<<n)-2; st > 0; st --) {
        for (int i = 0; i < n; i ++) {
            if (!(st & (1<<i))) {
                int st2 = st ^ (1<<i);
                for (int j = 0; j < n; j ++) {
                    if (st & (1<<j)) {
                        f[st] = min(f[st], f[st2] + c[i][j]);
                    }
                }
            }
        }
    }
    for (int st = 0; st < (1<<n); st ++) {
        if (__builtin_popcount(st) == k) {
            ans = min(ans, f[st]);
        }
    }
    cout << ans << endl;
    return 0;
}