自动搬运

查看原文

来自洛谷，原作者为

	xfrvq **

搬运于2025-08-24 21:31:57，当前版本为作者最后更新于2025-08-18 11:36:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$m$ 很小，考虑最简单的状压 dp：依次考虑 $i=1,\cdots,n$ 行，维护 $i-1,i-2$ 行共 $2m$ 个位置是否可填，状态数 $O(2^{2m}n)$。

考虑优化状态数。若 $(i-2,j)$ 可填 $(i-1,j)$ 不可填没有用。对每列维护上个不可填行在 $i-1,i-2$ 还是 $\le i-3$，状态数 $O(3^mn)$。

先预处理所有的转移 $(S,T,w)$ 代表：第 $i-1$ 行的状态 $S$ 可贴 $w$ 张海报，转移到第 $i$ 行状态 $T$。只需枚举 $S$ 爆搜第 $i$ 行填法。

由于障碍的存在，实际转移不一定是 $S\to T$。转移第 $i$ 行前，先枚举每个 $T$，若与当前行障碍列撞了则设 $T$ 非法，否则将 $T$ 的所有障碍列，上个不可填行修改为 $i$，设 $g_T=T'$。

最终转移时枚举 $(S,T)$，若 $T$ 合法则转移 $S\to g_T$。

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

int n,m,S,a[11],b[11],pw[11],f[155][60000],g[60000],ans;
vector<pair<int,int>> G[60000];
bool vis[155][15];

void dfs(int i,int c){
	if(i >= m){
		int T = 0;
		for(int i = 0;i < m;++i) T += b[i] * pw[i];
		G[S].emplace_back(T,c);
		return;
	}
	b[i] = max(a[i] - 1,0),dfs(i + 1,c);
	if(i + 1 < m && !max(a[i],a[i + 1]))
		b[i] = b[i + 1] = 2,dfs(i + 2,c + 1);
	if(i + 2 < m && max({a[i],a[i + 1],a[i + 2]}) < 2)
		b[i] = b[i + 1] = b[i + 2] = 2,dfs(i + 3,c + 1);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i = pw[0] = 1;i <= m;++i) pw[i] = pw[i - 1] * 3;
	for(S = 0;S < pw[m];++S){
		for(int i = 0,T = S;i < m;++i,T /= 3)
			a[i] = T % 3,g[i] |= (a[i] == 2) << i;
		dfs(0,0);
	}
	for(int i = 1;i <= n;++i)
		for(int j = 0;j < m;++j) scanf("%d",vis[i] + j);
	memset(f,-0x3f,sizeof f),f[0][pw[m] - 1] = 0;
	for(int i = 1;i <= n;++i){
		for(S = 0;S < pw[m];++S)
			for(int j = g[S] = 0,T = S;j < m;++j,T /= 3)
				if(T % 3 == 2 && vis[i][j]){ g[S] = -1; break; }
				else g[S] += (vis[i][j] ? 2 : T % 3) * pw[j];
		for(S = 0;S < pw[m];++S)
			for(auto[T,w] : G[S]) if(~g[T])
				ans = max(ans,f[i][g[T]] = max(f[i][g[T]],f[i - 1][S] + w));
	}
	printf("%d\n",ans);
	return 0;
}