E. Cleaning Robot（dp）

题目 参考

题意

给定2*n的01矩阵，1表示有灰尘，0表示无灰尘。机器人在(0,0)点出发，且点(0,0)没有灰尘。每次机器人会选择离他最近的灰尘点，并过去清除。清除后，再继续找下一个离他最近的灰尘点，一直到所有的灰尘都清理完毕。

但是如果同时存在两个点离机器人距离最近，那么机器人会故障。

问题来了，应该手工清理多少灰尘点，才能使机器人顺利地清理所有的灰尘。输出机器人最多能清理的灰尘数量。

思路

由于只有2行，我们可以预见，机器人的清理顺序是从左到右的。 出现2个灰尘点离机器人最近，当前仅当

• 机器人在第i行
• 灰尘点1在第i行，第j列
• 灰尘点2在第1-i行，第j-1列

定义dp[i][j][0]表示当前在第j行第i列，且对面的点无灰尘点， 定义dp[i][j][1]表示当前在第j行第i列，且对面的点有灰尘点

dp[i][j][0]可以从dp[i-1][j][0]（横向移动一格），dp[i-1][1-j][1]（先纵向移动，再横向移动）转移得到

dp[i][j][1]可以从dp[i-1][j][0]（横向移动一格）转移得到

代码

#include 
using namespace std;
#define ll long long
#define pcc pair
#define inf 0x3f3f3f3f
const int maxn = 200010;

int n;
char s[2][maxn];
int dp[maxn][2][2];
void solve() {
    scanf("%d", &n);
    for (int i = 0; i