自动搬运

查看原文

来自洛谷，原作者为

	UltiMadow Well I do.

搬运于2025-08-24 21:36:30，当前版本为作者最后更新于2020-04-17 10:53:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题解思路&部分代码实现来自这篇日报

终于过了，调了3h，写个题解纪念一下

这道题让我感到了什么叫真正的毒瘤

这题呢，看一眼数据范围，大概是插头dp

那我们就要考虑如何设计状态了

显然，本题中只记录轮廓线的插头状态是不够的，因为每个点的权值是由它周围的八个点的状态决定的，所以我们还要记录轮廓线的路径，也就是轮廓线上是放障碍还是炮台还是路径

我们记轮廓线上如果是障碍则为状态 0，如果是路径则为状态 1，如果是炮台则为 3

当然，我们发现插头状态仅记录左括号（记为1），右括号（记为2），和无插头（记为0）是不够的，因为本题中可能有没有括号和它匹配的插头，我们称其为独立插头（记为3）

我们又发现炮台的数量还有个限制，于是还要加一个状态记录炮台的数量

接下来，就是喜闻乐见的大力分类讨论时间啦

（当然，如果你没有做过这个题，那么建议你先去做一下，因为本题插头使用括号表示法）

我们记 $pl1$ 为右插头，记 $pl2$ 为下插头

1. 这个点 $pl1=0$ 且左边是路径或 $pl2=0$ 且上边是路径
   这种情况显然需要用障碍去堵住
   那么，显然只有无左插头且无下插头的情况是合法的
   接下来，只要转移这个点放炮台或障碍就行了

2. 这个点是障碍点
   这应该是最简单的一种
   显然只有无左插头且无下插头的情况是合法的
   直接转移即可

3. 这个点是非障碍点
   （疯狂的地方开始了）
   1）若 $pl1=0$ 且 $pl2=0$
   $\quad$ 则可以添加炮台，或者新建一个联通分量，或者不走
   2）若 $pl1=0$ 或 $pl2=0$
   $\quad$ 则直接延伸插头即可
   3）若 $pl1=1$ 且 $pl2=1$
   $\quad$ 则需要向右寻找一个右括号换成左括号并删除当前插头
   4）若 $pl1=2$ 且 $pl2=2$
   $\quad$ 则需要向左寻找一个左括号换成右括号并删除当前插头
   5）若 $pl1=1$ 且 $pl2=2$
   $\quad$ 不合法，因为这样会形成闭合回路
   6）若 $pl1=2$ 且 $pl2=1$
   $\quad$ 直接删除插头即可
   7）若 $pl1=1$ 且 $pl2=3$ 或 $pl1=3$ 且 $pl2=1$
   $\quad$ 则需要向右寻找一个右括号替换成独立插头并删除当前插头
   8）若 $pl1=2$ 且 $pl2=3$ 或 $pl1=3$ 且 $pl2=2$
   $\quad$ 则需要向左寻找一个左括号替换成独立插头并删除当前插头
   9）若 $pl1=3$ 且 $pl2=3$
   $\quad$ 直接删除插头即可

4. 这个点是起点或者终点
   1）若 $pl1=0$ 且 $pl2=0$
   $\quad$ 则需要新建一个独立插头
   2）若 $pl1=1$ 且 $pl2=0$ 或 $pl1=0$ 且 $pl2=1$
   $\quad$ 则需要向右寻找一个右括号替换成独立插头并删除当前插头
   3）若 $pl1=2$ 且 $pl2=0$ 或 $pl1=0$ 且 $pl2=2$
   $\quad$ 则需要向左寻找一个左括号替换成独立插头并删除当前插头
   4）若 $pl1=3$ 且 $pl2=0$ 或 $pl1=0$ 且 $pl2=3$
   $\quad$ 直接删除插头即可

以上是大力分类

接下来，我们来讲讲点权的事情

如果经过这个点，由于我们只知道轮廓线上的周围四个点的情况，所以只能加上这四个点中炮台的个数

如果这个点放障碍，不加，直接传下去就行

如果这个点放炮台，我们就要加上轮廓线上路径的个数，那为啥这样直接加是对的呢？

我们如果不经过一个点，我们可以直接把它设置成障碍，这样，一个炮台的贡献就是轮廓线上的周围四个点中路径的个数

该解释的都解释了，我们来看代码吧

#include<bits/stdc++.h>
#define MAXN 25
#define p 100007
#define int long long
using namespace std;
int n,m,K,now,pre;
char c[MAXN][MAXN];
int head[p+3],nxt[1<<24];
int f[2][1<<24],fst[2][3][1<<24];
int cnt[2];
void insert(int state1,int state2,int state3,int val)
{
	int ha=((((1ll*state1<<16)|state2)<<4)|state3)%p+1;//哈希
	for(int i=head[ha];i;i=nxt[i])
		if(fst[now][0][i]==state1&&fst[now][1][i]==state2&&fst[now][2][i]==state3)
		{
			f[now][i]=max(f[now][i],val);
			return;
		}
	f[now][++cnt[now]]=val;
	fst[now][0][cnt[now]]=state1;
	fst[now][1][cnt[now]]=state2;
	fst[now][2][cnt[now]]=state3;//三个状态
	nxt[cnt[now]]=head[ha];
	head[ha]=cnt[now];
}//hash表
int left(int state,int pos,int val)
{//向左寻找左括号
	int tot=1;
	while(true)
	{
		int pl=(state>>(pos<<1))&3;
		if(pl==2)tot++;if(pl==1) tot--;
		if(!tot)return state^(pl<<(pos<<1))^(val<<(pos<<1));
		pos--;
	}
}
int right(int state,int pos,int val)
{//向右寻找右括号
	int tot=1;
	while(true)
	{
		int pl=(state>>(pos<<1))&3;
		if(pl==1)tot++;if(pl==2) tot--;
		if(!tot)return state^(pl<<(pos<<1))^(val<<(pos<<1));
		pos++;
	}
}
char tmp[MAXN][MAXN];
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&K);
	for(int i=0;i<n;i++)scanf("%s",c[i]);
	if(n<m)
	{//n<m的时候把地图转90度
		memcpy(tmp,c,sizeof(c));
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				c[j][i]=tmp[i][j];
		swap(n,m);
	}
	cnt[0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<=cnt[now];j++)
			fst[now][0][j]<<=2;
		for(int j=1;j<=cnt[now];j++)
			fst[now][1][j]=(fst[now][1][j]^(((fst[now][1][j]>>(m+1<<1))&3)<<(m+1<<1)))<<2;//更新上一行的状态
		for(int j=0;j<m;j++)
		{
			pre=now;now^=1;cnt[now]=0;
			memset(head,0,sizeof(head));//注意初始化
			for(int k=1;k<=cnt[pre];k++)
			{
				int sta=fst[pre][0][k],stb=fst[pre][1][k],stc=fst[pre][2][k];
				int val=f[pre][k];
				if(sta>=(1<<(m+1<<1)))continue;
				int pl1=(sta>>(j<<1))&3;//right
				int pl2=(sta>>(j+1<<1))&3;//down
				int r=(stb>>(j<<1))&3;//右状态
				int ur=(stb>>(j+1<<1))&3;//右上状态
				int u=(stb>>(j+2<<1))&3;//上状态
				int ul=(stb>>(j+3<<1))&3;//左上状态
				int now=(sta^(pl1<<(j<<1))^(pl2<<(j+1<<1)));
				if((!pl1&&r==1)||(!pl2&&u==1))//1
				{
					if(pl1||pl2)continue;
					insert(now,stb^(ur<<(j+1<<1)),stc,val);//放障碍
					if(stc<K&&c[i][j]=='.')
						insert(now,stb^(ur<<(j+1<<1))^(3<<(j+1<<1)),stc+1,val+(r==1)+(ur==1)+(u==1)+(ul==1));//放炮台
				}
				else if(c[i][j]=='#'){if(!pl1&&!pl2)insert(now,stb^(ur<<(j+1<<1)),stc,val);}//2
				else if(c[i][j]=='.')//3
				{
					if(!pl1&&!pl2)//1)
					{
						if(stc<K)
							insert(now,stb^(ur<<(j+1<<1))^(3<<(j+1<<1)),stc+1,
								val+(r==1)+(ur==1)+(u==1)+(ul==1));//放炮台
						insert(now^(1<<(j<<1))^(2<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));//走
						insert(now,stb^(ur<<(j+1<<1)),stc,val);//不走
					}
					else if(!pl1&&pl2)//2）
					{
						insert(now^(pl2<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
						insert(now^(pl2<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					}
					else if(pl1&&!pl2)//2）
					{
						insert(now^(pl1<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
						insert(now^(pl1<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					}
					else if(pl1==1&&pl2==1)//3）
						insert(right(now,j,1),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(pl1==2&&pl2==2)//4）
						insert(left(now,j,2),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(pl1==2&&pl2==1)//6）
						insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(pl1==1&&pl2==3)//7）
						insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(pl1==2&&pl2==3)//8）
						insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(pl1==3&&pl2==1)//7）
						insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(pl1==3&&pl2==2)//8）
						insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(pl1==3&&pl2==3)//9）
						insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
				}
				else if(c[i][j]=='S'||c[i][j]=='T')//4
				{
					if(c[i][j]=='S'&&!pl1&&!pl2)//1）
					{
						insert(now^(3<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
						insert(now^(3<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					}
					else if(c[i][j]=='T'&&!pl1&&!pl2)//1）
					{
						insert(now^(3<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
						insert(now^(3<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					}
					else if(!pl1&&pl2==1)//2）
						insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(!pl1&&pl2==2)//3）
						insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(pl1==1&&!pl2)//2）
						insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(pl1==2&&!pl2)//3）
						insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(pl1==3&&!pl2)//4）
						insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
					else if(!pl1&&pl2==3)//4）
						insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
							val+(r==3)+(ur==3)+(u==3)+(ul==3));
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=cnt[now];i++)//统计答案
		if(!fst[now][0][i])
			ans=max(ans,f[now][i]);
	printf("%lld",ans);
	return 0;
}