P6883 [COCI2016-2017#3] Kroničan

一眼丁真：一道简单的入门的小清新状压好题。

分析

根据题意，每一个杯子只有有水或没水这两种状态。很容易想到用二进制去表示。有水为 $0$，没水为 $1$。

举个例子，有两个杯子所有杯子都没有水，那么状态为 $11$。

设 $dp[i]$ 表示从初始状态到状态 $i$ 所需的最小代价。

另外我们可以想到一个性质，例如说 $x$ 倒入 $y$ 中，$z$ 再倒往 $y$ 中，$y$ 倒入 $k$ 中与 $x$ 倒入 $y$ 中，$y$ 再倒往 $k$ 中，$z$ 倒往 $y$ 中，$y$ 有再一次倒入 $k$ 中是等价的。也就是倒入一个空杯子中与倒往这个杯子没空的时候可能是一样的。所以对于每一个状态 $i$，若当前有一个水杯没有水并且在上一步有水，则肯定是倒给了当前所有有水的杯子中的其中一个，而不是倒入没水的杯中。就不用算重复的情况了。

那么我们很容易想出转移方程：

$$dp[i] = \min(dp[i \oplus (1 << j)] + c[j][k], dp[i])$$

其中 $j$ 表示当前没有水的水杯，$k$ 表示当前有水的水杯，当然 $0 \le j, k < n$。下标从 $0$ 开始。而 $i \oplus (1 << j)$ 表示能转移到 $i$ 这个状态的状态。

初始化。

根据题意和定义 $dp[0] = 0$，其余则为正无穷。

答案就是在合法的状态中取最小值。

$0$ 的个数小于等于 $k$ 的状态即为合法。

当然，有一个小地方要注意，从 $x$ 杯倒入 $y$ 杯的价值可能不等于从 $y$ 杯 倒入 $x$ 杯的价值。

时间复杂度 $O(2ⁿⁿ2)$。对于这题够用了。

Code

下面的 __builtin_popcount(i) 是求出 $i$ 在二进制下有多少个 $1$。

顺便告诉你，吸个氧就逼近最优解了。

#include <bits/stdc++.h>
using namespace std;

int n, k, dp[(1 << 20) + 5], c[25][25];

int main() {
cin >> n >> k;
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i < n; i++)//下标从 0 开始。
for (int j = 0; j < n; j++)
cin >> c[i][j];
dp[0] = 0;
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if (i & (1 << j))//如果 j 这一杯没水。
for (int k = 0; k < n; k++)
if (!(i & (1 << k)))//找到当前有水的杯子，可能在上一步 j 的水倒入了 $k$。
dp[i] = min(dp[i], dp[(i - (1 << j))] + c[j][k]);//一定是 c[j][k]
}
}
int ans = 1e9;
for (int i = 0; i < (1 << n); i++)
if (__builtin_popcount(i) >= n - k)//也可以写成 n - __builtin_popcount(i) <= k，就是需要 0 的个数小于等于 k，或 1 的个数大于等于 k。
ans = min(ans, dp[i]);
cout << ans;
return 0;
}

后记

CSP2023 后的第一篇题解还是随机跳题来的捏。

若蒟蒻有空，会解答评论区的问题的。QwQ。

蒟蒻可能有笔误，欢迎大佬们来纠正。