Educational Codeforces Round 136 (Rated for Div. 2) E.Cleaning Robot（基础dp）

题目

两行n列，也就是2*n(n<=2e5)的格子，每个位置初始值不是0就是1

一开始机器人在(0,0)的位置，每次机器人会选择一个曼哈顿距离最近的1的位置，

将其变为0，表示将一个脏的地方打扫干净了，

然后再选择下一个曼哈顿距离最近的位置，直至打扫完所有的位置

但是，如果在某一时刻，曼哈顿距离最近的位置有多个，机器人会崩溃

现在问，最少删去多少个初始局面的1，使得机器人在工作过程中不会崩溃

输出最多保留的初始局面的1的个数

思路来源

cls的反例

题解

dp[i][0/1]表示，当前在第i列第j(0/1)行的时候，只考虑[i,n]列的初始局面，最小要删除多少个1，

转移的话，考虑相邻的两个格子的1的情况，

对于(列,行)(x,y)来说，

1. 如果(x,y^1)和(x+1,y)都有1，

则可以尝试一下删掉其中某个1，然后往右走到子局面

2. 如果(x,y^1)没有1，也就是同列相邻行没有1，显然可以往右走一步

3. 如果(x,y^1)有1，但(x+1,y)没有1，直觉感觉是直接贪心走到相邻1即可，但是，有反例

9
010011001
001001010

ans:6

所以，还是需要讨论删掉这个1和不删掉这个1，两种情况

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=2e5+10;
char s[2][N];
int n,one,dp[N][2];
int solve(int x,int y){
    if(x>=n-1)return 0;
    if(~dp[x][y])return dp[x][y];
    int &ans=dp[x][y];ans=0;
    if(s[y^1][x] && s[y][x+1])ans=min(solve(x+1,y),solve(x+2,y^1))+1;
    else if(s[y^1][x])ans=min(solve(x+1,y)+1,solve(x+2,y^1));
    else ans=solve(x+1,y);
    return ans;
}
int main(){
    cin>>n;
    for(int i=0;i<2;++i){
        cin>>s[i];
        for(int j=0;j<n;++j){
            one+=(s[i][j]=='1');
            s[i][j]-='0';
        }
    }
    memset(dp,-1,sizeof dp);
    cout<<one-solve(0,0)<<endl;
    return 0;
}
/*
9
010011001
001001010
*/