# C. Robot in a Hallway (recursion/prefix sum/dynamic programming)

2022-08-06 09:23:06Luo gkv

## 题意

Ask according to the requirements,Traverse all the grid,And meet the above conditions under the condition of,最少需要多少时间.

1<=m<=200000
1<=a[i][[j]<=1000000000

## 思路

1.1The finish on the second line

1.2The finish in the first line

Total feasible route has a lot of,If violence computing enumeration,会TLE.

We will route,Split into red line+橙色路线.
The red line is snakeskin walk,The orange line isUGlyph walk a.

2.1The orange line recursive relations

``````dp_end[ed] = max(a[2][ed], a[1][ed]+1);
``````

``````dp_end[i] = dp_end[i+2] + 2;// Because the end away from the2个单位,需要加2
dp_end[i] = max(dp_end[i], a[2][i]);// 新增点 a[2][i]
dp_end[i] = max(dp_end[i], a[2][i+1] + 1);// 新增点 a[2][i+1] + 1
// 下面的countRefers to the orange line grid Numbers.
dp_end[i] = max(dp_end[i], a[1][i+1] + count);// 新增点 a[1][i+1]
dp_end[i] = max(dp_end[i], a[1][i] + count + 1);// 新增点 a[1][i]
``````

2.2The recursion relation of red line
The recursion relation of red line is relatively more simple,直接模拟即可.

``````dp_start[1] = a[1][1];// 初始点
for (int i = 2; i <= m; ++i) {

// The red line,走到第i列,所需要的最少时间.
dp_start[i] = dp_start[i-1];
cur = 3 - cur;

step = max(step + 1, a[cur][i-1]);// 向上/下 走一格
dp_start[i] = max(dp_start[i], step);

step = max(step + 1, a[cur][i]);// 向右 走一格
dp_start[i] = max(dp_start[i], step);
}
``````

2.3Calculate the minimum time

Good computing red line and orange line,You can calculate the final result.
Red route from starting point to the red line end,需要的最小时间.
The orange line said from the orange line starting point,走到终点,需要的最小时间.
The cost of the current route time is
max(Red line need time+Walk to the end of time,The orange line)

``````ans = min(ans, max(dp_start[i] + (m - i) * 2 + 1, dp_end[i]));
``````

• 要区分mFor the odd and even number of scene
• Grid least time need locka[i][j],So it is in the firsta[i][j]+1Time to visit.
• 注意取long long,The data overflow

PS：Too sleepy last night didn't finish writing ran to go to bed,Drop points, it doesn't matter233

## 代码

``````#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200010;

int m;
ll a[3][maxn];
ll dp_start[maxn];
ll dp_end[maxn];

void cal_end(int ed, int st, bool sub_flag, int cur) {

int count = 0;// The current orange route node number
if (sub_flag) {
// 如果终点,There's a list of,需要额外考虑
--ed;
dp_end[ed] = a[cur][ed];
dp_end[ed] = max(dp_end[ed], a[cur][m] + 1);
dp_end[ed] = max(dp_end[ed], a[3-cur][m] + 2);
dp_end[ed] = max(dp_end[ed], a[3-cur][ed] + 3);
count += 4;
} else {

dp_end[ed] = a[cur][ed];
dp_end[ed] = max(dp_end[ed], a[3-cur][ed] + 1);
count += 2;
}
// dp_end[i]Said the finish in the firstiColumns of the orange line,的最小花费时间
for (int i = ed - 2; i >= st; i -= 2) {

count += 2;// 添加2元素
dp_end[i] = dp_end[i+2] + 2;// Because the end away from the2个单位,需要加2
dp_end[i] = max(dp_end[i], a[cur][i]);// 新增点 a[cur][i]
dp_end[i] = max(dp_end[i], a[cur][i+1] + 1);// 新增点 a[cur][i+1]
// 下面的 3-cur是取 上/下 一列
dp_end[i] = max(dp_end[i], a[3-cur][i+1] + count);// 新增点 a[3-cur][i+1]
dp_end[i] = max(dp_end[i], a[3-cur][i] + count + 1);// 新增点 a[3-cur][i]
count += 2;// 添加2元素
}
}
void cal_start() {

ll step = 0;
int cur = 1;
dp_start[1] = a[1][1];
// dp_start[i] 表示 红色路线,走到第i列,所需要的最少时间.
for (int i = 2; i <= m; ++i) {

dp_start[i] = dp_start[i-1];
cur = 3 - cur;

step = max(step + 1, a[cur][i-1]);// 向上/下 走一格
dp_start[i] = max(dp_start[i], step);

step = max(step + 1, a[cur][i]);// 向右 走一格
dp_start[i] = max(dp_start[i], step);
}
}
void debug() {

printf("a:\n");
for (int i = 1; i <= 2; ++i) {

for (int j = 1; j <= m; ++j) {

printf("%lld ", a[i][j]);
}
printf("\n");
}
printf("dp_start:\n");
for (int i = 1; i <= m; ++i) {

printf("%lld ", dp_start[i]);
}
printf("\ndp_end:\n");
for (int i = 1; i <= m; ++i) {

printf("%lld ", dp_end[i]);
}
printf("\n");
}
void solve() {

scanf("%d", &m);
for (int i = 1; i <= 2; ++i) {

for (int j = 1; j <= m; ++j) {

scanf("%lld", &a[i][j]);
if (a[i][j]) ++a[i][j];// 方便处理,非0值都加1
}
}
for (int i = 1; i <= m; ++i) {

dp_start[i] = 0;
dp_end[i] = 0;
}
cal_start();
cal_end(m, 1, m % 2 == 0, 2);
cal_end(m, 2, m & 1, 1);

// debug();

int cur = 1;
ll ans = max(dp_start[1] + (m - 1) * 2 + 1, dp_end[1]);
for (int i = 2; i <= m; ++i) {

cur = 3 - cur;
ans = min(ans, max(dp_start[i] + (m - i) * 2 + 1, dp_end[i]));
}
printf("%lld\n", ans);
}

int main() {

int t;
// t = 1;
scanf("%d", &t);
int cas = 1;
while (t--) {

solve();
}
}
/* 99 2 0 1 0 0 */
``````

## 最后

Think of my article is good,weixin gongzhonghao搜 The other isdebug,关注下,Happy together brush problem~