自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 21:53:46，当前版本为作者最后更新于2022-07-18 14:21:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$nm\leq50,m\leq n$ 说明 $m\leq7$，一眼状压。

设 $f_{i,j,k}$ 为第 $i$ 行状态为 $j$，$i-1$ 行状态为 $k$ 且 $1$ 至 $i-1$ 行全部有油库相邻的最小代价， $dp_{i,j,k}$ 为最小个数。

那么 $f$ 的转移方程显然：

$$f_{i,j,k}=\min_{0\leq l<2^m}\{f_{i-1,k,l}+sum_{i,j}\text{ }(\#)\} $$

其中 $sum_{i,j}$ 是第 $i$ 行状态为 $j$ 的花费， $dp$ 跟着 $f$ 转移一下就可以了。

$\#$ 是转移的条件，上面挤不下了，这里来写：

对于 $f_{i-1,k,l}$，第 $1$ 行至第 $i-2$ 行一定全部有油库相邻，只要考虑第 $i-1$ 列，所以 $\#$ 是 (j|k|l|k<<1|k>>1)。

代码实现如下：

#include <bits/stdc+.h>
using namespace std;
const int N = 10, M = 55;
int f[M][1 << N][1 << N], dp[M][1 << N][1 << N], sum[M][1 << N], a[M][N], n, m, ans1 = INT_MAX, ans2 = INT_MAX;
int main() {
	cin >> n >> m;
	memset(f, 0x3f, sizeof f);
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			cin >> a[i][j];
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j < 1 << m; j ++)
			for (int k = 0; k < m; k ++)
				if (j & 1 << k) sum[i][j] += a[i][k + 1];
	for (int i = 0; i < 1 << m; i++)
		f[1][i][0] = sum[1][i], dp[1][i][0] = __builtin_popcount(i);
	for (int i = 2; i <= n; i ++)
		for (int j = 0; j < 1 << m; j ++)
			for (int k = 0; k < 1 << m; k ++)
				for (int l = 0; l < 1 << m; l ++)
					if (((j | k | l | k << 1 | k >> 1) & (1 << m) - 1)== (1 << m) - 1) {
						int t = f[i - 1][k][l] + sum[i][j], p = dp[i - 1][k][l] + __builtin_popcount(j);
						if (f[i][j][k] > t || f[i][j][k] == t && dp[i][j][k] > p)
							f[i][j][k] = t, dp[i][j][k] = p;
					}
	for (int i = 0; i < 1 << m; i ++)
		for (int j = 0; j < 1 << m; j ++)
			if (((i | j | i << 1 | i >> 1) & (1 << m) - 1) == (1 << m) - 1)
				if (ans1 > f[n][i][j] || f[n][i][j] == ans1 && dp[n][i][j] < ans2)
					ans1 = f[n][i][j], ans2 = dp[n][i][j];
	cout << ans2 << ' ' << ans1 <<'\n';
    system("pause")
	return 0;
}