题解：P6883 [COCI2016-2017#3] Kroničan
看到 $1 \le N,K \le 20$ 的数据范围，不难想到状态压缩 $\texttt{dp}$。设 dp[i] 表示所有玻璃杯的状态为 $i$ 时的最小花费。
由于是最小花费，初始化时会将所有的 dp[i] 默认为 INF，然后再特殊处理 dp[0] 的值。那么会有一个问题—对于状态 $i$ 的第 $j$ 位，什么时候表示有水呢？根据布尔变量的思想，容易先入为主的将有水时的状态设为 $1$。但是需要思考的是，倘若此时将 dp[0] = 0，那么就表示所有的水杯（再加上引入的编号为 $0$ 的水杯）均无水时最小花费为 $0$。这样既与题面中的所有的水杯初始均装有一定的水矛盾，在计算时又无法通过 dp[0] 的值去转移。因此，我们便将状态 $i$ 的第 $j$ 位有水时设为 $0$。
状态转移还是比较显然的，倘若 $j$ 杯中有水，那么可以将杯中的水倒入 $k$ 中。这里又有一个小问题，枚举状态的 $i$ 去表示转移前还是转移后呢？我们再将问题的本质聚焦到状态的含义的设置上，由于 $0$ 表示有水，所以当 $i$ 表示转移前时，比较难去处理转移后的状态（原来某一位的 $1$ 将标记为 $0$，而若是 $0$ 则不需要改变），因此本题解选择比较容易的表示转移后的状态的方法。总结一下，也就是说，当满足 i & (1 << j) == 0 且 i & (1 << k) == 0 时，进行如下转移：dp[i] = min (dp[i],dp[i ^ (1 << j)] + a[j][k])。
最后在统计答案时，由于状态设置的特殊性，需要统计每一状态下 $0$ 的个数，若小于等于 $k$，则进行答案的更新。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,INF,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 20;
const int MOD = 1e9 + 7;
inline int read ();
int n,k,ans = INF,a[MAX][MAX],dp[1 << 20];
int count (int x);
int main ()
{
n = read ();k = read ();
for (int i = 0;i < n;++i)
for (int j = 0;j < n;++j) a[i][j] = read ();
init (dp);
dp[0] = 0;
for (int i = 1;i < (1 << n);++i)
{
for (int j = 0;j < n;++j)
{
if (!(i & (1 << j))) continue;
for (int k = 0;k < n;++k)
if (!(i & (1 << k)))
dp[i] = min (dp[i],dp[i ^ (1 << j)] + a[j][k]);
}
}
for (int i = 1;i < (1 << n);++i)
if (count (i) <= k) ans = min (ans,dp[i]);
printf ("%d\n",ans);
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
int count (int x)
{
int cnt = 0;
while (x)
{
x &= (x - 1);
++cnt;
}
return n - cnt;
}
|
后记：由于笔者还是个蒟蒻，倘若有大佬可以写出状态 $i$ 的第 $j$ 位有水时设为 $1$ 时且十分简洁的代码（我尝试了好久，但是一直没调出来 $\texttt{qwq}$），欢迎私信！
