比赛链接
https://www.51nod.com/contest/problemList.html#!contestId=72&randomCode=147206
这次考试的题非常有质量
这次考试暴露了非常多的问题，心理给自己设限，知识点不熟练等等问题。
只拿了暴力的分。
这道题复习状压dp，状压dp一般可以处理一个集合内的问题
这道题是第三题，但我放在这一题
因为这一题反而最水……
我当时一看到数据范围20，马上想到状压dp
但是一方面因为觉得这是第三题，应该会比较难，而且前面两道题都做不出来，所以心理障碍
很大，就没有怎么很深入的去想（不过说到底还是状压dp不熟练）。
考完后，5分钟秒了，发现这是我做过最水的状压dp题。
这道题和TSP问题很类似（不懂的可以百度一下，或者我博客里面有）
用1表示魔力还在，0表示没有了。
那么dp[S] = min(dp[S], dp[S^(1<<j)] + c[j][i])
#include<bits/stdc++.h> #define REP(i, a, b) for(register int i = (a); i < (b); i++) #define _for(i, a, b) for(register int i = (a); i <= (b); i++) using namespace std; const int MAXM = (1 << 20) + 10; const int MAXN = 30; int c[MAXN][MAXN], dp[MAXM]; int num(int x) { return !x ? 0 : 1 + num(x & (x - 1)); } //二进制中1的个数 int main() { int n, k; scanf("%d%d", &n, &k); REP(i, 0, n) REP(j, 0, n) scanf("%d", &c[i][j]); int ans = 1e9; memset(dp, 0x3f, sizeof(dp)); //这里初始化要注意 dp[(1<<n)-1] = 0; for(register int S = (1 << n) - 1; S >= 0; S--) { if(num(S) < k) continue; REP(i, 0, n) if(S & (1 << i)) REP(j, 0, n) if(!(S & (1 << j))) dp[S] = min(dp[S], dp[S^(1<<j)] + c[j][i]); if(num(S) == k) ans = min(ans, dp[S]); } printf("%d\n", ans); return 0; }
这是第二题。我觉得第一题才是最难的，最后讲
原文：https://www.cnblogs.com/sugewud/p/9822933.html