我是靠谱客的博主 斯文小懒猪,最近开发中收集的这篇文章主要介绍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
001001010ans: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
*/
最后
以上就是斯文小懒猪为你收集整理的Educational Codeforces Round 136 (Rated for Div. 2) E.Cleaning Robot(基础dp)的全部内容,希望文章能够帮你解决Educational Codeforces Round 136 (Rated for Div. 2) E.Cleaning Robot(基础dp)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复