CF1739 EDU E

· · 题解

题意：给定一个 2\times n 的房间，有一部分格子是脏的，一个机器人从 (1,1) 出发，每次选择最近的脏格子前往并清理。但机器人如果确定目标时发现两个以上一样最近的脏格子会寄，问最多留下几个格子。

（距离的定义是横坐标之差的绝对值加上纵坐标之差的绝对值）

由于是 2\times n ，很容易想到机器人应该不会向左走。（向左走意味着有左边有一个格子离他最近，那么你是从左边走过来的，肯定有一次离他距离1甚至0）

那么考虑DP，其实这时已经有大量设计状态的方式了。

为了状态的方便，我们试着转换一下题意，改为找一条路径使得路径上没有一个脏格子与另外两个脏格子距离最短且一样，并使得这条路径上的脏格子最多。那么路径之外的脏格子可以全部抹除。

在这里我设 f_{i,j} 表示走到第 i 列第 j 格时最多能清除的格子。

那么每走到一个格子，我们有两种方案：

1.无视同一列的另一个格子，直接向右走。(这里 a_{i,j} 表示第 i 列 j 行是不是脏格子）

f_{i+1,j}= \max\{f_{i+1,j}\ ,\ f_{i,j}+a_{i+1,j}\}

2.换一行。换一行的必要条件是另一行是脏格子且下一列的同行不是脏格子（或者将那里的脏格子抹除）。值得注意的是可能出现能换行但另一行不是脏格子的情况，如

x0
01

（机器人在 x 处）

但此时你可以先向右移动再向下，两种情况等价。

为了方便解释，我给出一个例子。

   1  2  3
a  x  1  1
b  1  1  1

如果要换行，那么我们要求 2a 不是脏格子，那么我们的机器人到了 2b 之后就必须往右走。

所以如果换行，那么有

f_{i+2,!j}= \max\{f_{i+2,!j}\ ,\ f_{i,j}+a_{i,!j}+a_{i+1,!j}+a_{i+2,!j}\}

同理，如果需要在下一列就换行也是和下下列再换行等价的。所以该状态转移方程成立。

#include<bits/stdc++.h>

using namespace std;

const int maxn=200010;
int a[maxn][2];
int f[maxn][2];//第i列 从上/下进入
char s[2][maxn];

inline int Max(int a,int b){
    return a>b?a:b; 
}

int main(){
    int n;scanf("%d",&n);
    for(int i=0;i<2;i++)
        scanf("%s",s[i]+1);
    for(int i=0;i<2;i++)
        for(int j=1;j<=n;j++) a[j][i]=s[i][j]-'0';

    /*for(int i=0;i<2;i++){
        for(int j=1;j<=n;j++) {
            cout<<a[j][i];
        }
        puts("");
    }*/

    for(int i=0;i<2;i++) for(int j=1;j<=n;j++) f[j][i]=-(1<<30);
    f[1][0]=0;

    for(int i=1;i<=n;i++){
        for(int j=0;j<=1;j++){
            f[i+1][j]=Max(f[i+1][j],f[i][j]+a[i+1][j]); //直接向右走 另外一格有则清
            if(a[i][!j]) //如果想要换一行，那么下一行必须得是脏的，且下一列的同行得清掉 
                f[i+2][!j]=Max(f[i+2][!j],f[i][j]+a[i][!j]+a[i+1][!j]+a[i+2][!j]);
        }
    }
    return printf("%d\n",Max(Max(f[n+1][0],f[n+1][1]),Max(f[n+2][0],f[n+2][1]))),0;
}