cf Educational Codeforces Round 133 C. Robot in a Hallway

原题：
There is a grid, consisting of 2 rows and m columns. The rows are numbered from 1 to 2 from top to bottom. The columns are numbered from 1 to m from left to right.

The robot starts in a cell (1,1). In one second, it can perform either of two actions:

• move into a cell adjacent by a side: up, right, down or left;
• remain in the same cell.
  The robot is not allowed to move outside the grid.

Initially, all cells, except for the cell (1,1), are locked. Each cell (i,j) contains a value $a_{i,j}$ — the moment that this cell gets unlocked. The robot can only move into a cell (i,j) if at least $a_{i,j}$ seconds have passed before the move.

The robot should visit all cells without entering any cell twice or more (cell (1,1) is considered entered at the start). It can finish in any cell.

What is the fastest the robot can achieve that?

Input
The first line contains a single integer t (1≤t≤10^4) — the number of testcases.

The first line of each testcase contains a single integer m (2≤m≤2⋅105) — the number of columns of the grid.

The i-th of the next 2 lines contains m integers $a_{i,1}$,$a_{i,2}$,…,$a_{i,m}$ (0≤ai,j≤10^9) — the moment of time each cell gets unlocked. a1,1=0. If $a_{i,j}$=0, then cell (i,j) is unlocked from the start.

The sum of m over all testcases doesn’t exceed 2⋅10^5.

Output
For each testcase, print a single integer — the minimum amount of seconds that the robot can take to visit all cells without entering any cell twice or more.

Example
input
4
3
0 0 1
4 3 2
5
0 4 8 12 16
2 6 10 14 18
4
0 10 10 10
10 10 10 10
2
0 0
0 0

output
5
19
17
3

中文：
有一个2 * m大小的网格，一个机器人最开始在$a_{1,1}$的位置，机器人每次可以上下左右移动或者原地等待在当前的位置上，每次移动或原地等待花费一个单位的时间。每个格子中有一个数字，表示要移动到该格子时至少要等到时间超过或者等于该格子上的数量。现在问你，在机器人遍历完所有格子后，最少花费多少时间？

代码：

#include 
using namespace std;
typedef long long ll;
 
const int maxn = 2e5 + 2;
const ll inf = 999999999999;
 
ll grid[3][maxn];
ll snake[maxn];
ll counter_clk[maxn];
ll clk[maxn];
ll len[maxn];
int t, n;
 
int main() {
    ios::sync_with_stdio(false);
 
    cin >> t;
    while(t--) {
        cin >> n;
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= n; j++){
                cin >> grid[i][j];
                if (i == 1 && j == 1) {
                    continue;
                }
                grid[i][j]++;
            }
        }
        for (int i= 0; i <= n + 1; i++) {
            clk[i] = 0;
            counter_clk[i] = 0;
            snake[i] = 0;
            len[i] = 0;
        } 
        ll cnt = 0;
        int row = 1;
        for (int i = 1; i < n; i++) {
            snake[i] = snake[i-1];
            row = 3 - row;
 
            cnt = max(cnt + 1, grid[row][i]);// up or down
            snake[i] = max(snake[i], cnt);
            cnt = max(cnt + 1, grid[row][i + 1]);// right
            snake[i] = max(snake[i], cnt);
        }
        for (int i = n; i >= 1; i--) {
            len[i] = len[i+1] + 2;
        }
        
        // clockwise
        clk[n] = max(grid[2][n], grid[1][n] + 1);
 
        // counter-clockwise
        counter_clk[n] = max(grid[1][n], grid[2][n] + 1);
    
        for (int i = n - 1; i >= 1; i--) {
            // clockwise
            clk[i] = max(clk[i], grid[1][i] + len[i + 1] - 1 + 2); // grid[1][i]最大
            clk[i] = max(clk[i + 1] + 1, clk[i]); // clk[i + 1]及其之后的格子中的值最大
            clk[i] = max(clk[i], grid[2][i]); // grid[2][i]最大
 
            // counter-clockwise
            counter_clk[i] = max(counter_clk[i], grid[2][i] + len[i + 1] - 1 + 2);
            counter_clk[i] = max(counter_clk[i + 1] + 1, counter_clk[i]);
            counter_clk[i] = max(counter_clk[i], grid[1][i]);
        }
 
        ll ans = clk[1];
        if (n % 2) {
            ll tmp = max(snake[n - 1] + 1, grid[2][n]); // down
            ans = min(ans, tmp);
        } else {
            ll tmp = max(snake[n - 1] + 1, grid[1][n]); // up
            ans = min(ans, tmp);
        }
        for (int i = 1; i < n - 1; i++) {
            if (i % 2 == 0) { // clk
                ans = min(ans, max(snake[i] + 2 * (n - i) - 1, clk[i + 1]));
            } else {
                ans = min(ans, max(snake[i] + 2 * (n - i) - 1, counter_clk[i + 1]));
            }
        }
        cout << ans << endl;
    }
    
    return 0;
}
 
/*
5
0 4 8 12 16
2 6 10 14 18
 
19
 
1
4
0 16 2 7
4 5 3 8
 
17
 
1
4
0 10 10 10
10 10 10 10
17
 
2
0 1
2 0
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

解答：

cf上有一道类似的题目
Vasya And The Mushrooms

此题目属于上面那道题目的变种，规律一样，但是状态转移不太好想出来。
接着上面那道题的基础，如果机器人要想遍历完全部的格子，那么机器人只有两种走法：

1. 走蛇形，即先向下走，再向右，再向上，再向右，再向下，以此类推。
2. 第二种环形走法，是一直向右，走到头后拐弯，再一直向左。

比如下面为蛇形走法

下面为环形走法

可以将两种走法结合起来，先蛇形再环形，比如下面这张图：

设snake[i]表示使用蛇形走法，走到第i + 1列时所消耗的时间。
比如snake[1]表示先向下走一步，再向右走一步，此时在grid[2][2]时所用的时间。
设clk[i]为从第1行第i列作为起始点，向右走到头，再向下走回第2行第i列所用时间，表示顺势走
counter_clk[i]同上，表示逆时针走，即从第2行第i列走到第1行第i列。

那么，可以先提前计算出所有的snake[i]、clk[i]以及counter_clk[i]。
然后枚举从哪一点开始使用环形走法，更新最小时间即可。

目前关键在于两点

第一，现在考虑用类似ans = min(ans, snake[i] ? clk[i])这样的方式来计算，这里问号表示某种状态转移的计算方式（先仅考虑顺时针环形走）
。
假设到第i列，我们可以计算得到的snake[i]的值，如果clk[i]表示从第i列开始走，走回第i列所使用的时间。那么状态转移方程怎么表示才能得到将snake[i]和clk[i]连接起来的完整结果？

第二，clk[i]（counter_clk[i]同理）表示的时从第i列作为起点开始走，走到最右侧，再拐弯回到第i列。以grid[1][i]作为起点，会有这样一个问题。即初始的时间应该时多少？假如grid[1][i]的值为10，那么在clk[i]的起始的计算时间应该是10吗？但是，假如在第i列执行环形走之前，就已经花费了远超过10个单位的时间，此时clk[i]设置为10明显是不合理的。那么clk[i]应该怎么计算？或者clk[i]保存的值到底是什么？这个问题又依赖于第一个问题中状态转移方程是怎么设置的。

从第一个问题开始考虑，转移方程要如何计算，需要什么变量。

通过观察发现。
如果要把路径分成两部分，比如snake和clk两部分，如果snake部分消耗的时间多于clk部分，即在clk部分的每一个格子都不需要任何等待时间，那么使用snake[i]走到第i列后，后面使用环形走法每走一步都是在前面走过的步数上增加一个单位的移动时间而已。

即snake[i] + 2 * (n - i) - 1 就是最终时间，比如共有5列，i等于2，此时snake[2] + 2 * ( 5- 2) - 1，snake[2]后面的算式所走的步数表示grid[1][3] -> grid[1][4]-> grid[1][5]-> grid[2][5]-> grid[2][4]-> grid[2][3] 正好5步

如果走到snake[i]，并在i位置使用环形走法时，发现有的格子的值非常打需要等待，那么肯定是以环形走法中最大的值作为计算的时间，在通过逐步移动走回到i列。

即，这里设置clk[i]表示从第1行第i列开始走，并且以grid[1][i]中所标记的时间作为初始，顺时针走回到第2行第i列时所花费的时间。

比如共有5列，grid[1][5]为6， gird[2][5]为3，那么clk[5]的值为7，即从grid[1][5]走到grid[2][5]需要6 + 1的时间。如果grid[1][5]为3，grid[2][5]为6，那么clk[5]的值就是6，因为从grid[1][5]走到grid[2][5]需要原地等待时间变成grid[2][5]的值。

上面的clk[i]如何计算？也是一个递推方程，从n向1推导，假设已经计算出了clk[i + 1]，考虑第i列，那么有如下三种情况：

1. grid[i][1]的值为grid[i][1]，clk[i + 1]所走过的所有值以及grid[i][2]这三者中最大的，那么时间肯定时从grid[i][1]开始计算，后面再走(n - i) + 1步，即为所消耗的总时间。
2. clk[i+1]所用的值最大，那么时间从clk[i + 1]所使用的时间开始累计，再加上走到grid[2][1]的时间，即clk[i + 1] + 1
3. grid[i][2]的值最大，可想而知，无论前面走了多久，最后都以grid[i][2]的时间为准。

由此，状态转移方程可以写作
$ans=min(ans,max(snake[i]+2\ast (n-i)-1,clk[i+1]));$

同理再计算一遍逆时针的情况即可