题解：CF1739E Cleaning Robot

· · 题解

Cleaning Robot

考虑 dp 状态

发现我们到某一行有两种情况，并且对当前这一行有影响的只有后面的两列。 考虑分情况讨论。 假设我们在 $(i,j)$。 1. 如果 $(i,j\oplus1)$ 没有。 那么我可以直接去下一行不受影响。 $dp_{i,j}=dp_{i+1,j}

  1. 如果 i,j\oplus 1 有但是第 i+1 列都没有。

两种选择，将另一行上的手动清理掉，或者不清理，让机器人自己转移到另一行。

dp_{i,j}=\min({{\color{blue}dp_{i+1,j\oplus1}},{\color{Purple}dp_{i+1,j}+1}})

（对应同颜色路径）

  1. 如果 i,j\oplus 1 和 i+1,j\oplus 1 有，但 i+1,j 没有。

和 \text{2} 相同，因为 (i+1,j\oplus1) 是否有不会对我的 \text{2} 抉择造成任何影响，所以不用考虑。

  1. 如果 i,j\oplus 1 和 i+1,j 有，但 i+1,j\oplus1 没有。

此时出现了矛盾点，必须清除其中的一个。

dp_{i,j}=\min{({\color{Gold}dp_{i+1,j\oplus1}+1},{\color{blue}{dp_{i+2,j}+1}})}

  1. 如果这三处地方都有。

这时我们有三条路线，两种情况。

如果我不想换行，就说明我要把另外两个都手动删掉。

否则我可以选择从上面绕，还是从下面绕

但是不难发现，橙色的路线存在问题，就是如果在问号所在地有一处垃圾，那就说明 (i+1,j) 是不能走的，也就是说我们无法预测这里的状态，但是不用担心，我们观察紫色的路线，发现他和橙色的终点一样，也就是说两种路线造成的影响以及花费其实是相同的，因此我们完全不用在意橙色路线，无脑选择紫色即可。

同时我们依然存在情况二的蓝色路径。

dp_{i,j}=\min{({\color{purple}dp_{i+2,j\oplus1}+1},{\color{blue}{dp_{i+2,j}+2}})}

综上转移即可。

\text{CODE}

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,mp[N][3],f[N][3],sum;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)mp[i][0]=getchar()-'0';
    getchar();
    for(int i=1;i<=n;i++)mp[i][1]=getchar()-'0';
    for(int i=1;i<=n;i++)sum+=mp[i][0]+mp[i][1];
    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<2;j++)
        {
            if(mp[i][j^1]==0)f[i][j]=f[i+1][j];
            else
            {
                if(mp[i+1][j]==0)f[i][j]=min(f[i+1][j^1],f[i+1][j]+1);
                else if(mp[i+1][j^1]==0)f[i][j]=min(f[i+2][j],f[i+2][j^1])+1;
                else f[i][j]=min(f[i+2][j]+2,f[i+2][j^1]+1);
            }
        }
    }
    cout<<sum-f[1][0]<<"\n";
    return 0;
}