P7668 [JOI2018] Dango Maker 题解

· · 题解

前言

模拟赛的 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 不选 / 选横的饺子串 / 选竖的饺子串。

动态转移方程显然：

dp_{i,0}=\max\{dp_{i-1,0},dp_{i-1,1},dp_{i-1,2}\} dp_{i,1}=\max\{dp_{i-1,0},dp_{i-1,1}\}+f(x,y) dp_{i,2}=\max\{dp_{i-1,0},dp_{i-1,2}\}+g(x,y)

其中 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;
}