自动搬运

查看原文

来自洛谷，原作者为

	菲斯斯夫斯基 几时归去，作个闲人。对一张琴，一壶酒，一溪云。

搬运于2025-08-24 22:32:01，当前版本为作者最后更新于2024-05-29 15:42:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

模拟赛的 T2，20 min 想出来的，怎么在 T2 放绿题。

思路

首先观察一波冲突多的情况:

RGWRGW
GWRGWR
WRGWRG
RGWRGW
GWRGWR
WRGWRG

考虑用 R、G 和 W 的其中一个字母来计算贡献。就是说假如选了一串，那么把这一串的贡献记录在其中一个字母的位置上。

可以发现 R 和 W 如果取了竖的饺子串，那么会影响上面的 $2$ 行和下面的 $2$ 行不能选横的饺子串。比如下面这个：选了左下角的 W 就不能选右上角的 W 了。可以自己手搓一下 R 和 G 的情况。

RGW
GWR
WRG

但是 G 只会影响右上一个和左下一个，处理起来比较方便。于是我们选 G 来计算贡献。

然后就是很明显的 dp 了，设 $dp_{i,0/1/2}$ 分别表示当前的 G 不选 / 选横的饺子串 / 选竖的饺子串。

动态转移方程显然：

其中 $f(x,y)$ 和 $g(x,y)$ 指 $(x,y)$ 这个点能不能放横的 / 竖的饺子串。

代码

不过注意是在斜线上会发生冲突，所以要在斜线上 dp。

#include<bits/stdc++.h>
using namespace std;
const int N=3010;
int n,m,ans;
int dp[N<<1][5];
char c[N][N];
bool f(int x,int y)
{
	return y>=2&&y<=m-1&&c[x][y-1]=='R'&&c[x][y]=='G'&&c[x][y+1]=='W';
} 
bool g(int x,int y)
{
	return x>=2&&x<=n-1&&c[x-1][y]=='R'&&c[x][y]=='G'&&c[x+1][y]=='W';
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>c[i][j];
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<=max(n,m);j++)
			dp[j][0]=dp[j][1]=dp[j][2]=dp[j][3]=0;
		int id=0,x=1,y=i;
		while(x>=1&&x<=n&&y>=1&&y<=m)
		{
			id++;
			dp[id][0]=max(dp[id-1][0],max(dp[id-1][1],max(dp[id-1][2],dp[id-1][3])));
			dp[id][1]=max(dp[id-1][0],dp[id-1][1])+f(x,y);
			dp[id][2]=max(dp[id-1][0],dp[id-1][2])+g(x,y);
			x++,y--;
		}
		ans+=max(dp[id][0],max(dp[id][1],max(dp[id][2],dp[id][3])));
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=max(n,m);j++)
			dp[j][0]=dp[j][1]=dp[j][2]=dp[j][3]=0;
		int id=0,x=i,y=m;
		while(x>=1&&x<=n&&y>=1&&y<=m)
		{
			id++;
			dp[id][0]=max(dp[id-1][0],max(dp[id-1][1],max(dp[id-1][2],dp[id-1][3])));
			dp[id][1]=max(dp[id-1][0],dp[id-1][1])+f(x,y);
			dp[id][2]=max(dp[id-1][0],dp[id-1][2])+g(x,y);
			x++,y--;
		}
		ans+=max(dp[id][0],max(dp[id][1],max(dp[id][2],dp[id][3])));
	}
	cout<<ans;
	return 0;
}