【题解】Kronican

题目描述
Mislav有N个无限体积的杯子，每一个杯子中都有一些水。Mislav想喝掉所有的水，但他不想喝超过K杯水。Mistrav能做的就是将一个杯子中的水倒入另一个杯子中。 不幸的是，挑选哪两个杯子进行倒水操作对Mislav来说很重要，因为并非所有的杯子都离他一样远。更准确地说，从i号杯子向j号杯子倒水所付出的代价为Cij。 帮助Mislav找到他需要付出的总代价的最小值。

输入格式
第一行输入包含整数N和K（1≤K≤N≤20）。表示水杯的总数和Mislav最多能喝多少杯。 接下来N行每行包含N个整数Cij（0≤Cij≤1e5）。第i+1行的第j个整数表示从第i个杯子第j个杯子倒水所需要付出的代价。保证Cii等于0。

输出格式
输出一个整数。表示Mislav需要付出的总代价的最小值。

样例
样例输入1
3 3
0 1 1
1 0 1
1 1 0
样例输出1
0
样例输入2
3 2
0 1 1
1 0 1
1 1 0
样例输出2
1
样例输入3
5 2
0 5 4 3 2
7 0 4 4 4
3 3 0 1 2
4 3 1 0 5
4 5 5 5 0
样例输出3
5
范围
n<=20

因为看到$n<=20$，一般就是状压了
然后直接用$2^n$个01状态表示某个杯子里还有没有水
每次枚举一个有水的杯子，再枚举一个有水的杯子，把前面那个杯子倒到后面那个，完成转移
时间复杂度$O(2^n\ast n^2)$
然后会$tle$
所以想到一个小技巧，每次只枚举状态中所有的"1"
差不多就过了

Code：

#pragma GCC optimize ("-Ofast")
#include <bits/stdc++.h>
#define maxn 25
#define maxm 2000010
using namespace std;
int n, m, w[maxn][maxn], pos[maxm], power[maxn], num[maxm], dp[maxm];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int lowbit(int x){ return x & -x; }

int main(){
	freopen("pb.in", "r", stdin);
	freopen("pb.out", "w", stdout);
	n = read(), m = read();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			w[i][j] = read();
	power[0] = 1, pos[1] = 1;
	for (int i = 1; i <= n; ++i) power[i] = power[i - 1] << 1, pos[power[i]] = i + 1;
	for (int i = 0; i < power[n]; ++i)
		for (int j = i; j; j -= lowbit(j)) ++num[i];
	for (int i = 0; i < power[n]; ++i) dp[i] = 1e9;
	dp[power[n] - 1] = 0;
	int ans = 1e9;
	for (int i = power[n] - 1; i >= 0; --i){ //printf("num[%d]=%d\n", i, num[i]);
		if (num[i] <= m) ans = min(ans, dp[i]);
		for (int s1 = i; s1; s1 -= lowbit(s1)){
			int j = pos[lowbit(s1)];
			for (int s2 = i; s2; s2 -= lowbit(s2)){
				int k = pos[lowbit(s2)];
				if (j != k) dp[i ^ power[j - 1]] = min(dp[i ^ power[j - 1]], dp[i] + w[j][k]);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}