自动搬运

查看原文

来自洛谷，原作者为

	Figo17 蒻是一种态度

搬运于2025-08-24 22:27:18，当前版本为作者最后更新于2021-08-27 16:27:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P7171 题解

2021.10.29 修改了一些语言表述问题。

题意：

有 $n\times m$ 个格子，一些是"#"，一些是"."，每次可以将连续个"#"涂色，不可重复涂色，求最少涂抹次数。

分析：

一道经典的 dp 问题，考虑普通状压转移过于复杂，还会超时，所以使用轮廓线 dp。

我们设 $dp_{i,j,k}$ 为在扫描前 i 行第 j 个元素时，前 m 个数的二进制状态（0 为横着涂，1 为竖着涂，不可涂色部分默认为 0）为 k 时的答案贡献。

（此时二进制状态从低位到高位应分别对应前 m 的数、前 m-1 的数等等，以此类推）

（对于“前 i 的数”的顺序的定义，可以理解为矩阵一般的搜索顺序）

解决：

确定状态后，我们考虑该如何转移。

对于当前所找的元素，如果为"#"，则 $dp_{i,j+1,k>>1}$（即下个元素横着涂）可由 $dp_{i,j,k}$（若未超界且当前元素为横）或 $dp_{i,j,k}+1$（若未超界且当前元素为竖）转移过去；

以此类推，$dp_{i,j+1,(k>>1)+(1<<m-1)}$（即下个元素竖着涂）也可以这样转移。

如果当前元素为"."，则直接转移贡献即可。

（可能有点难读懂，那就展现读者强大的阅读能力吧！）

代码：

#include<bits/stdc++.h>
using namespace std;
int dp[1005][15][2050];
int n,m,M;
char c[1005][15];
int ans;
int maxn=1000000007;
int main()
{
	cin>>n>>m;M=1<<m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>c[i][j];
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<M;k++)
				dp[i][j][k]=maxn;
	
	if(c[1][1]=='#') dp[1][1][0]=dp[1][1][1<<m-1]=1;
	else dp[1][1][0]=0;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<M;k++)
			{
				if(dp[i][j][k]>=maxn) continue;
				int nj=j%m+1,ni=i;
				if(j==m) ni=i+1;
				if(c[ni][nj]=='#')
				{
					if(nj>1&&!(k&1<<m-1)&&c[i][j]=='#') dp[ni][nj][k>>1]=min(dp[ni][nj][k>>1],dp[i][j][k]);
					else dp[ni][nj][k>>1]=min(dp[ni][nj][k>>1],dp[i][j][k]+1);
					if(ni>1&&(k&1)&&c[ni-1][nj]=='#') dp[ni][nj][(k>>1)+(1<<m-1)]=min(dp[ni][nj][(k>>1)+(1<<m-1)],dp[i][j][k]);
					else dp[ni][nj][(k>>1)+(1<<m-1)]=min(dp[ni][nj][(k>>1)+(1<<m-1)],dp[i][j][k]+1);
				}
				else dp[ni][nj][k>>1]=min(dp[ni][nj][k>>1],dp[i][j][k]);
			}
	
	ans=maxn;
	for(int i=0;i<M;i++)
		ans=min(ans,dp[n][m][i]);

	cout<<ans;
	return 0;
}

朴素奇丑的代码。

谢谢观看！！